Sparse Covers for Sums of Indicators

Abstract

For all $n,\epsilon >0$, we show that the set of Poisson Binomial distributions on $n$ variables admits a proper $\epsilon$-cover in total variation distance of size $n^2+n\cdot (1/\epsilon {)}^{O({\log }^2(1/\epsilon ))}$, 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.

arXiv commentPTRF, to appear

Cited by in corpus (1)

• Query Complexity of Approximate Equilibria in Anonymous Games