Built on

Enumerative Combinatorics
Richard Stanley · 1997
Earlier work this paper cites.
Restriction access
Zeev Dvir, Anup Rao, Avi Wigderson, and Amir Yehudayoff · 2012
Earlier work this paper cites.

Similar

Population recovery and partial identification
Avi Wigderson and Amir Yehudayoff · 2012
Cited alongside, same era.
Finding heavy hitters from lossy or noisy data
Lucia Batman, Russell Impagliazzo, Cody Murray, and Ramamohan Paturi · 2013
Cited alongside, same era.

Then

A polynomial time algorithm for lossy population recovery
Ankur Moitra and Michael Saks · 2013
Later among the works it cites.
Improved noisy population recovery, and reverse bonami-beckner inequality for sparse functions
Shachar Lovett and Jiapeng Zhang · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2016

Noisy population recovery in polynomial time

De, Anindya, Saks, Michael, Tang, Sijian

Understand

In the noisy population recovery problem of Dvir et al., the goal is to learn an unknown distribution $f$ on binary strings of length $n$ from noisy samples.

For some parameter $\mu \in [0,1]$, a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with probability $(1-\mu)/2$.
We assume an upper bound $k$ on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error $\varepsilon$.
It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other.