English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Schur Polynomials are families of symmetric polynomials that have beenclassically studied in Combinatorics and Algebra alike. They play a centralrole in the study of Symmetric functions, in Representation theory [Sta99], inSchubert calculus [LM10] as well as in Enumerative combinatorics [Gas96, Sta84,Sta99]. In recent years, they have also shown up in various incarnations inComputer Science, e.g, Quantum computation [HRTS00, OW15] and Geometriccomplexity theory [IP17].  However, unlike some other families of symmetric polynomials like theElementary Symmetric polynomials, the Power Symmetric polynomials and theComplete Homogeneous Symmetric polynomials, the computational complexity ofsyntactically computing Schur polynomials has not been studied much. Inparticular, it is not known whether Schur polynomials can be computedefficiently by algebraic formulas. In this work, we address this question, andshow that unless \emph{every} polynomial with a small algebraic branchingprogram (ABP) has a small algebraic formula, there are Schur polynomials thatcannot be computed by algebraic formula of polynomial size. In other words,unless the algebraic complexity class $\mathrm{VBP}$ is equal to the complexityclass $\mathrm{VF}$, there exist Schur polynomials which do not have polynomialsize algebraic formulas.  As a consequence of our proof, we also show that computing the determinant ofcertain \emph{generalized} Vandermonde matrices is essentially as hard ascomputing the general symbolic determinant. To the best of our knowledge, theseare one of the first hardness results of this kind for families of polynomialswhich are not \emph{multilinear}. A key ingredient of our proof is the study ofcomposition of \emph{well behaved} algebraically independent polynomials with ahomogeneous polynomial, and might be of independent interest.

Schur Polynomials do not have small formulas if the Determinant doesn't!