Homogeneous formulas and symmetric polynomials

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.