Inequalities and tail bounds for elementary symmetric polynomials

  • Parikshit Gopalan ,
  • Amir Yehudayoff

MSR-TR-2014-131 |

This paper studies the elementary symmetric polynomials over the reals. We show that if two consecutive elementary symmetric polynomials are small in absolute value, then so are all the elementary symmetric polynomials that follow. 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.