Homogeneous formulas and symmetric polynomials (Q649096)

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.