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 -