Schur Polynomials Do Not Have Small Formulas If the Determinant does not
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Schur Polynomials Do Not Have Small Formulas If the Determinant does not. / Chaugule, Prasad; Kumar, Mrinal; Limaye, Nutan; Mohapatra, Chandra Kanta; She, Adrian; Srinivasan, Srikanth.
In: Computational Complexity, Vol. 32, No. 1, 3, 2023.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Schur Polynomials Do Not Have Small Formulas If the Determinant does not
AU - Chaugule, Prasad
AU - Kumar, Mrinal
AU - Limaye, Nutan
AU - Mohapatra, Chandra Kanta
AU - She, Adrian
AU - Srinivasan, Srikanth
N1 - Publisher Copyright: © 2023, The Author(s), under exclusive licence to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - 68W30
KW - Algebraic independence
KW - Formula complexity
KW - Generalized Vandermonde determinant
KW - Jacobian
KW - Lower bound
KW - Schur polynomial
KW - Taylor expansion
U2 - 10.1007/s00037-023-00236-x
DO - 10.1007/s00037-023-00236-x
M3 - Journal article
AN - SCOPUS:85159936848
VL - 32
JO - Computational Complexity
JF - Computational Complexity
SN - 1016-3328
IS - 1
M1 - 3
ER -
ID: 382685159