ECCC-Report TR14-019https://eccc.weizmann.ac.il/report/2014/019Comments and Revisions published for TR14-019en-usSat, 15 Feb 2014 03:45:07 +0200
Paper TR14-019
| Inequalities and tail bounds for elementary symmetric polynomials |
Parikshit Gopalan,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2014/019This 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.Sat, 15 Feb 2014 03:45:07 +0200https://eccc.weizmann.ac.il/report/2014/019