Loading jsMath...
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: 7091
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