### Abstract

In the noisy population recovery problem of Dvir et al. [6], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. A noisy sample with parameter μ ϵ [0,1] is generated by selecting a sample from f, and independently flipping each coordinate of the sample with probability (1-μ)/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 ϵ. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We describe an algorithm that for each μ > 0, provides the desired estimate of the distribution in time bounded by a polynomial in k, n and 1/ϵ improving upon the previous best result of poly(klog log k, n, 1/ϵ) due to Lovett and Zhang [9]. Our proof combines ideas from [9] with a noise attenuated version of Möbius inversion. The latter crucially uses the robust local inverse construction of Moitra and Saks [11].

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |

Publisher | IEEE Computer Society |

Pages | 675-684 |

Number of pages | 10 |

ISBN (Electronic) | 9781509039333 |

DOIs | |

State | Published - Dec 14 2016 |

Event | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States Duration: Oct 9 2016 → Oct 11 2016 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2016-December |

ISSN (Print) | 0272-5428 |

### Other

Other | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
---|---|

Country | United States |

City | New Brunswick |

Period | 10/9/16 → 10/11/16 |

### Keywords

- Fourier transform
- Population recovery
- Reverse Bonami-Beckner inequality

### ASJC Scopus subject areas

- Computer Science(all)

## Fingerprint Dive into the research topics of 'Noisy Population Recovery in Polynomial Time'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016*(pp. 675-684). [7782982] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2016-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2016.77