License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.14
URN: urn:nbn:de:0030-drops-125660
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12566/
Chaugule, Prasad ;
Kumar, Mrinal ;
Limaye, Nutan ;
Mohapatra, Chandra Kanta ;
She, Adrian ;
Srinivasan, Srikanth
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't
Abstract
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 [Stanley, 1999], in Schubert calculus [Ledoux and Malham, 2010] as well as in Enumerative combinatorics [Gasharov, 1996; Stanley, 1984; Stanley, 1999]. In recent years, they have also shown up in various incarnations in Computer Science, e.g, Quantum computation [Hallgren et al., 2000; Ryan O'Donnell and John Wright, 2015] and Geometric complexity theory [Ikenmeyer and Panova, 2017].
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 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 VBP is equal to the complexity class 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 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 multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.
BibTeX - Entry
@InProceedings{chaugule_et_al:LIPIcs:2020:12566,
author = {Prasad Chaugule and Mrinal Kumar and Nutan Limaye and Chandra Kanta Mohapatra and Adrian She and Srikanth Srinivasan},
title = {{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {14:1--14:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-156-6},
ISSN = {1868-8969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12566},
URN = {urn:nbn:de:0030-drops-125660},
doi = {10.4230/LIPIcs.CCC.2020.14},
annote = {Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound}
}
|
Keywords: |
|
Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound |
|
Collection: |
|
35th Computational Complexity Conference (CCC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
17.07.2020 |
