Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-019 | 14th February 2014 18:50

#### Inequalities and tail bounds for elementary symmetric polynomials

TR14-019
Authors: Parikshit Gopalan, Amir Yehudayoff
Publication: 15th February 2014 03:45
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 independent, that may be useful in the context of derandomization. We also provide examples of $t$-wise independent distributions for which our bounds are essentially tight.