Is Randomness Necessary for Adaptive Data Analysis?

arXiv:2607.07085 · cs.CR, cs.DS, cs.LG · Submitted 2026-07-08 · Read on arXiv

Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer

cs.CR, cs.DS, cs.LG

Submitted: 2026-07-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

Random Oracle — 30× in this paper
Adaptive Data Analysis — 18× in this paper
Accuracy — 9× in this paper · explained in 1 episode
Generalization — 8× in this paper · explained in 13 episodes
Adam — 3× in this paper · explained in 2 episodes
Differential Privacy — 3× in this paper · explained in 4 episodes
Hypergraph — 3× in this paper · explained in 2 episodes
Fingerprinting — 2× in this paper · explained in 2 episodes
Post-Selection — 2× in this paper · explained in 2 episodes
Adaptive Mechanism — 1× in this paper · explained in 1 episode
Adaptivity — 1× in this paper · explained in 1 episode
Algorithmic Stability — 1× in this paper · explained in 1 episode
Annual ACMSIAM Symposium on Discrete Algorithms — 1× in this paper
Clustering — 1× in this paper · explained in 2 episodes
Decode — 1× in this paper · explained in 2 episodes
Sample Complexity — 1× in this paper · explained in 15 episodes
Symposium on Foundations of Computer Science — 1× in this paper

Sources

Related papers