Homogeneous Formulas and Symmetric Polynomials |
| |
Authors: | Pavel Hrube? Amir Yehudayoff |
| |
Affiliation: | (1) Department of Mathematical and Computer Sciences Loyola University Chicago Chicago, IL 60626, |
| |
Abstract: | We investigate the arithmetic formula complexity of the elementary symmetric polynomials Skn{S^k_n} . We show that every multilinear homogeneous formula computing Skn{S^k_n} has size at least kW(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for Skn{S^k_n} have size at least 2W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sn2n{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 Skn{S^k_n} can be computed by homogeneous formulas of size kO(logk)n{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: | |
本文献已被 SpringerLink 等数据库收录! |
|