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

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

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

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

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

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

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

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