Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-019 | 14th February 2014 18:50

Inequalities and tail bounds for elementary symmetric polynomials

RSS-Feed




TR14-019
Authors: Parikshit Gopalan, Amir Yehudayoff
Publication: 15th February 2014 03:45
Downloads: 6804
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint