# Preserving Randomness for Adaptive Adversaries

Calvin Lab Auditorium

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm π€ππ on many adaptively chosen inputs. For each execution, the chosen input to π€ππ remains hidden from the steward, but the steward chooses the randomness of π€ππ and, crucially, is allowed to modify the output of π€ππ. The notion of a steward is inspired by adaptive data analysis, introduced by Dwork et al. Suppose π€ππ outputs values in βd, has ββ error Ο΅, has failure probability Ξ΄, uses n coins, and will be executed k times. For any Ξ³>0, we construct a computationally efficient steward with ββ error O(Ο΅d), failure probability kΞ΄+Ξ³, and randomness complexity n+O(klog(d+1)+(logk)log(1/Ξ³)). To achieve these parameters, the steward uses a PRG for what we call the block decision tree model, combined with a scheme for shifting and rounding the outputs of π€ππ. (The generator is a variant of the INW generator.)

As applications of our steward, we give time- and randomness-efficient algorithms for estimating the acceptance probabilities of many adaptively chosen Boolean circuits and for simulating any algorithm with an oracle for πππππππΎ-π‘π―π― or π π―π―. We also give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least ΞΈ of a function F:{0,1}nβ{β1,1} using O(nlogn)β poly(1/ΞΈ) queries to F and O(n) random bits, improving previous work by Bshouty et al. Finally, we prove a randomness complexity lower bound of n+Ξ©(k)βlog(Ξ΄β²/Ξ΄) for any steward with failure probability Ξ΄β², which nearly matches our upper bounds in the case dβ€O(1).