Sparse Covers for Sums of Indicators

For all $n, ε>0$, we show that the set of Poisson Binomial distributions on $n$ variables admits a proper $ε$-cover in total variation distance of size $n^2+n \cdot (1/ε)^{O(\log^2 (1/ε))}$, which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games.

No reviews yet.

No comments yet.