Preserving Randomness for Adaptive Algorithms

Suppose $\mathsf{E}\mathsf{s}\mathsf{t}$ is a randomized estimation algorithm that uses $n$ random bits and outputs values in ${\mathbb{R}}^d$. We show how to execute $\mathsf{E}\mathsf{s}\mathsf{t}$ on $k$ adaptively chosen inputs using only $n + O(k \log(d + 1))$randombitsinsteadofthetrivial$nk$ (at the cost of mild increases in the error and failure probability). Our algorithm combines a variant of the INW pseudorandom generator (STOC '94) with a new scheme for shifting and rounding the outputs of $\mathsf{E}\mathsf{s}\mathsf{t}$. We prove that modifying the outputs of $\mathsf{E}\mathsf{s}\mathsf{t}$ is necessary in this setting, and furthermore, our algorithm’s randomness complexity is near-optimal in the case $d\le O(1)$. As an application, we give a randomness-efficient version of the Goldreich-Levin algorithm; our algorithm finds all Fourier coefficients with absolute value at least $\theta$ of a function $F:\{0,1{\}}^n\to \{-1,1\}$ using $O(n \log n) \cdot $\text{poly}$(1/\theta)$queriesto$F$and$O(n)$ random bits (independent of $\theta$), improving previous work by Bshouty et al. (JCSS '04).