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

Research output: Contribution to journalJournal articleResearchpeer-review

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.

Original languageEnglish
Article number3
JournalComputational Complexity
Volume32
Issue number1
ISSN1016-3328
DOIs
Publication statusPublished - 2023
Externally publishedYes

Bibliographical note

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

    Research areas

  • 68W30, Algebraic independence, Formula complexity, Generalized Vandermonde determinant, Jacobian, Lower bound, Schur polynomial, Taylor expansion

ID: 382685159