Preventing False Discovery in Interactive Data Analysis is Hard

Moritz Hardt, Jonathan Ullman

We show that, under a standard hardness assumption, there is no computationally efficient algorithm that given $n$ samples from an unknown distribution can give valid answers to $n…