TR19-172 Authors: Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Publication: 28th November 2019 08:40

Downloads: 188

Keywords:

Schur Polynomials are families of symmetric polynomials that have been

classically studied in Combinatorics and Algebra alike. They play a central

role in the study of Symmetric functions, in Representation theory [Sta99], in

Schubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,

Sta99]. In recent years, they have also shown up in various incarnations in

Computer Science, e.g, Quantum computation [HRTS00, OW15] and Geometric

complexity theory [IP17].

However, unlike some other families of symmetric polynomials like the

Elementary Symmetric polynomials, the Power Symmetric polynomials and the

Complete Homogeneous Symmetric polynomials, the computational complexity of

syntactically computing Schur polynomials has not been studied much. In

particular, it is not known whether Schur polynomials can be computed

efficiently by algebraic formulas. In this work, we address this question, and

show that unless \emph{every} polynomial with a small algebraic branching

program (ABP) has a small algebraic formula, there are Schur polynomials that

cannot be computed by algebraic formula of polynomial size. In other words,

unless the algebraic complexity class $\mathrm{VBP}$ is equal to the complexity

class $\mathrm{VF}$, there exist Schur polynomials which do not have polynomial

size algebraic formulas.

As a consequence of our proof, we also show that computing the determinant of

certain \emph{generalized} Vandermonde matrices is essentially as hard as

computing the general symbolic determinant. To the best of our knowledge, these

are one of the first hardness results of this kind for families of polynomials

which are not \emph{multilinear}. A key ingredient of our proof is the study of

composition of \emph{well behaved} algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.