Homogeneous formulas and symmetric polynomials (Q649096)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Homogeneous formulas and symmetric polynomials |
scientific article |
Statements
Homogeneous formulas and symmetric polynomials (English)
0 references
30 November 2011
0 references
The authors investigate the arithmetical complexity of the elementary polynomials \(S_n^k\), questions which were studied in particular by V. Strassen (1973), and E. Shamir and M. Snir (1979). Their main result is that every multilinear homogeneous formula computing \(S_n^k\) has size at least \(k^{\Omega (\log k)}n\), and the product-depth \(d\) multinear homogeneous formulas for \(S_n^k\) has size at least \(2^{\Omega(k^{1/d})}n\). This implies a ``superpolynomial separation'' between multilinear and multinear homogeneous formulas. The paper also answers questions of Nisan and Wigderson. The methods of proofs are algebraic and combinatorial.
0 references
symmetric polynomials
0 references
algebraic complexity
0 references