# Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery

arXiv: https://arxiv.org/abs/1410.1228 · HTML: https://mlsanity.com/paper/1410.1228/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2014.

## Built on by (most cited first, 30 of 35)

- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Adaptive Data Analysis in a Balanced Adversarial Model](https://mlsanity.com/paper/2305.15452/) (2023)
- [The Power of Sampling: Dimension-free Risk Bounds in Private ERM](https://mlsanity.com/paper/2105.13637/) (2021)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [Tight Bounds for Answering Adaptively Chosen Concentrated Queries](https://mlsanity.com/paper/2507.13700/) (2025)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)
- [Making Progress Based on False Discoveries](https://mlsanity.com/paper/2204.08809/) (2022)
- [Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model](https://mlsanity.com/paper/2301.09203/) (2023)
- [Loss Gradient Gaussian Width based Generalization and Optimization Guarantees](https://mlsanity.com/paper/2406.07712/) (2024)
- [Predicting adaptively chosen observables in quantum systems](https://mlsanity.com/paper/2410.15501/) (2024)
- [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025)

## Abstract (arXiv)

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 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 studied by Dwork et al., who showed how to answer tildeOmega(n2) queries efficiently, and also by Hardt and Ullman, who showed that answering tildeO(n3) queries is hard. We close the gap between the two bounds and 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 O(n2) adaptively chosen statistical queries. An implication of our results is that computationally efficient algorithms for answering arbitrary, adaptively chosen statistical queries may as well be differentially private. We obtain our results using a new connection between the problem of answering adaptively chosen statistical queries and a combinatorial object called an interactive fingerprinting code. In order to optimize our hardness result, we give a new Fourier-analytic approach to analyzing fingerprinting codes that is simpler, more flexible, and yields better parameters than previous constructions.