Spring 2017

Preserving Randomness for Adaptive Adversaries

Wednesday, March 8th, 2017 9:30 am10:30 am

Add to Calendar

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