Preserving Randomness for Adaptive Adversaries

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).