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.