Theory of Computing
-------------------
Title     : Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials
Authors   : Parikshit Gopalan and Amir Yehudayoff
Volume    : 16
Number    : 17
Pages     : 1-29
URL       : https://theoryofcomputing.org/articles/v016a017

Abstract
--------

We study the extent of independence needed to approximate the product
of bounded random variables in expectation. This natural question has
applications in pseudorandomness and min-wise independent hashing.

For random variables with absolute value bounded by 1, we give an
error bound of the form $\sigma^{\Omega(k)}$ when the input is
k-wise independent and $\sigma^2$ is the variance of their sum.
Previously, known bounds only applied in more restricted settings,
and were quantitively weaker. Our proof relies on a new analytic
inequality for the elementary symmetric polynomials $S_k(x)$ for
$x \in \R^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small
relative to $|S_{k-1}(x)|$ for some $k> 0$ then $|S_\ell(x)|$ is also
small for all $\ell > k$. We use this to give a simpler and more modular
analysis of a construction of min-wise independent hash functions and
pseudorandom generators for combinatorial rectangles due to Gopalan et
al., which also improves the overall seed-length.