Homogeneous formulas and symmetric polynomials
Preprint
Abstract
We investigate the arithmetic formula complexity of the elementary symmetric polynomials S(k,n). We show that every multilinear homogeneous formula computing S(k,n) has size at least k^(Omega(log k))n, and that product-depth d multilinear homogeneous formulas for S(k,n) have size at least 2^(Omega(k^{1/d}))n. Since S(n,2n) has a multilinear formula of size O(n^2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S(k,n) can be computed by homogeneous formulas of size k^(O(log k))n, answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Depth-3 arithmetic circuits over fields of characteristic zerocomputational complexity, 2001
- Lower bounds on arithmetic circuits via partial derivativescomputational complexity, 1996
- Fast Parallel Computation of Polynomials Using Few ProcessorsSIAM Journal on Computing, 1983
- Negation can be exponentially powerfulTheoretical Computer Science, 1980
- On the Parallel Evaluation of Multivariate PolynomialsSIAM Journal on Computing, 1979