Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC POLYNOMIALS:
Reports tagged with symmetric polynomials:
TR01-035 | 15th April 2001
Amir Shpilka

Affine Projections of Symmetric Polynomials

In this paper we introduce a new model for computing=20
polynomials - a depth 2 circuit with a symmetric gate at the top=20
and plus gates at the bottom, i.e the circuit computes a=20
symmetric function in linear functions -
$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20
elementary symmetric polynomial in $m$ ... more >>>


TR03-047 | 22nd June 2003
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such
representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ... more >>>


TR14-019 | 14th February 2014
Parikshit Gopalan, Amir Yehudayoff

Inequalities and tail bounds for elementary symmetric polynomials

This paper studies the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only $t$-wise ... more >>>


TR19-149 | 4th November 2019
Dean Doron, Pooya Hatami, William Hoza

Log-Seed Pseudorandom Generators via Iterated Restrictions

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>


TR22-139 | 15th October 2022
Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

On the VNP-hardness of Some Monomial Symmetric Polynomials

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>


TR22-157 | 16th November 2022
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Border complexity via elementary symmetric polynomials

Revisions: 1

In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>>


TR24-079 | 20th April 2024
Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for
deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ... more >>>


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