Homogeneous formulas and symmetric polynomials

Details Homogeneous formulas and symmetric polynomials Homogeneous formulas and symmetric polynomials

2009-07-15

arxiv.org/abs/0907.2621v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Homogeneous formulas and symmetric polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Homogeneous formulas and symmetric polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Homogeneous formulas and symmetric polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-364801