Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HOMOGENIZATION:
Reports tagged with Homogenization:
TR25-053 | 23rd April 2025
Amir Shpilka

On Approximate Symmetric Polynomials and Tightness of Homogenization Results

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 ... more >>>




ISSN 1433-8092 | Imprint