Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-123 | 7th October 2014 02:39

#### Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

TR14-123
Authors: Shachar Lovett, Jiapeng Zhang
Publication: 7th October 2014 03:20
Keywords:

Abstract:

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in \$\{0,1\}^n\$ with support of size \$k\$,
and given access only to noisy samples from it, where each bit is flipped independently with probability \$1/2-\eps\$,
estimate the original probability up to an additive error of \$\eps\$. We give an algorithm which solves this problem in time polynomial in \$(k^{\log \log k}, n, 1/\eps)\$.
This improves on the previous algorithm of Wigderson and Yehudayoff [FOCS 2012] which solves the problem in time polynomial in \$(k^{\log k}, n, 1/\eps)\$.
Our main technical contribution, which facilitates the algorithm, is a new reverse Bonami-Beckner inequality for the \$L_1\$ norm of sparse functions.

ISSN 1433-8092 | Imprint