# Sparse Covers for Sums of Indicators

arXiv: https://arxiv.org/abs/1306.1265 · HTML: https://mlsanity.com/paper/1306.1265/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2013.

## Built on by (most cited first, 2 of 2)

- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)

## Abstract (arXiv)

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.