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 n2+n · (1/ε)O(log2 (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.