Schur Polynomials Do Not Have Small Formulas If the Determinant does not

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

Schur Polynomials are families of symmetric polynomialsthat have been classically studied in Combinatorics and Algebra alike.They play a central role in the study of symmetric functions, in Representationtheory Stanley (1999), in Schubert calculus Ledoux & Malham(2010) as well as in Enumerative combinatorics Gasharov (1996); Stanley(1984, 1999). In recent years, they have also shown up in variousincarnations in Computer Science, e.g, quantum computation Hallgrenet al. (2000); O'Donnell & Wright (2015) and geometric complexitytheory Ikenmeyer & Panova (2017). However, unlike some other families of symmetric polynomials like theelementary symmetric polynomials, the power symmetric polynomialsand the complete homogeneous symmetric polynomials, the computationalcomplexity of syntactically computing Schur polynomials has notbeen studied much. In particular, it is not known whether Schur polynomialscan be computed efficiently by algebraic formulas. In this work,we address this question and show that unless every polynomial with asmall algebraic branching program (ABP) has a small algebraic formula,there are Schur polynomials that cannot be computed by algebraic formulaof polynomial size. In other words, unless the algebraic complexityclass VBP is equal to the complexity class VF, there exist Schur polynomialswhich do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinantof certain generalized Vandermonde matrices is essentially ashard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kindfor families of polynomials, which are not multilinear. A key ingredientof our proof is the study of composition of well behaved algebraicallyindependent polynomials with a homogeneous polynomial, which mightbe of independent interest.

OriginalsprogEngelsk
Artikelnummer3
TidsskriftComputational Complexity
Vol/bind32
Udgave nummer1
ISSN1016-3328
DOI
StatusUdgivet - 2023
Eksternt udgivetJa

Bibliografisk note

Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

ID: 382685159