Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-053 | 23rd April 2025 14:26

On Approximate Symmetric Polynomials and Tightness of Homogenization Results

RSS-Feed




TR25-053
Authors: Amir Shpilka
Publication: 23rd April 2025 14:27
Downloads: 128
Keywords: 


Abstract:

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results:

We first show that by making small modifications to the nonzero coefficients of the degree-K, N-variate elementary symmetric polynomial \sigma_{N,K}, one obtains a polynomial that can be computed by a monotone formula of size K^{O(\log K)} \cdot N.

As a corollary, we show that a result of Raz [Raz13] concerning the homogenization of algebraic multilinear or monotone formulas is tight.

Another corollary is that the monotone bounded rigidity of the inclusion matrix between K-subsets and N-K subsets of a universe of size N is small.



ISSN 1433-8092 | Imprint