We show a tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given *n* samples from an unknown distribution. A statistical query asks for the expectation of a predicate over the underlying distribution, and an answer to a statistical query is accurate if it is ``close'' to the correct expectation over the distribution. This question was recently considered by Dwork et al., who showed that *Ω ^{~}(n^{2})* queries can be answer efficiently, and also by Hardt and Ullman, who showed that answering

Full Version: | arxiv |

Bibtex: |
@inproceedings{SteinkeUllman2014, author = {Thomas Steinke and Jonathan Ullman}, title = {Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery}, booktitle = {}, year = {2014}, pages = {}, } |

Last updated on 7 Oct 2014 by Thomas Steinke.