Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

Thomas Steinke, Jonathan Ullman

We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given $n$ samples from an…