Preprint
Jul 2026
Is Randomness Necessary for Adaptive Data Analysis?
It is shown that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O}(n)$ queries.
Edith Cohen, Haim Kaplan, Yishay Mansour et al.
· 0 citations