Under the auspices of the Computational Complexity Foundation (CCF)

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

ISSN 1433-8092 | Imprint