Tight lower bounds for differentially private selection
Thomas Steinke, Jonathan Ullman
FOCS 2017
We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length Õ(log3 n). The best previously known seed length for this model is n1/2+o(1) due to Impagliazzo, Meka, and Zuckerman (FOCS’12). Our result generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM’13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f: f:{0.1}n →f:{0,1} computed by such a branching program, and k ∈ [n]; (Formula Presented.) where (Formula Presented.) is the standard Fourier transform over ℤn2. The base O(logn) of the Fourier growth is tight up to a factor of log logn.
Thomas Steinke, Jonathan Ullman
FOCS 2017
Mark Bun, Thomas Steinke, et al.
NeurIPS 2019
Boaz Barak, Yehuda Lindell, et al.
FOCS 2003
Stacey Truex, Nathalie Baracaldo, et al.
Informatik-Spektrum