Noisy Population Recovery in Polynomial Time

Anindya De, Michael Saks, Sijian Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages675-684
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period10/9/1610/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

    De, A., Saks, M., & Tang, S. (2016). Noisy Population Recovery in Polynomial Time. In 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