TR14-019 Authors: Parikshit Gopalan, Amir Yehudayoff

Publication: 15th February 2014 03:45

Downloads: 5038

Keywords:

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.