pdf icon
Volume 16 (2020) Article 17 pp. 1-29
Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials
Received: October 8, 2015
Revised: August 30, 2020
Published: December 24, 2020
Download article from ToC site:
[PDF (312K)] [PS (1660K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: pseudorandomness, $k$-wise independence, hashing, concentration, symmetric polynomials
Categories: pseudorandomness, $k$-wise independence, hashing, concentration, polynomials, polynomials - multivariate, inequalities, inequalities for elementary symmetric polynomials
ACM Classification: G.3
AMS Classification: 68Q87

Abstract: [Plain Text Version]

$ \newcommand{\R}{{\mathbb R}} $

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.