SCIENCE@home

Homogeneous Formulas and Symmetric Polynomials

P. Hrubes,A. Yehudayoff

Published 2009 in Computational Complexity

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(n2), 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-12 of 12 references · Page 1 of 1

CITED BY

Showing 1-51 of 51 citing papers · Page 1 of 1