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: 176
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