The Discrete Gaussian for Differential Privacy
Clément L. Canonne, Gautam Kamath, et al.
NeurIPS 2020
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.
Clément L. Canonne, Gautam Kamath, et al.
NeurIPS 2020
Mark Bun, Thomas Steinke, et al.
SODA 2017
Giuseppe Vietri, Grace Tian, et al.
ICML 2020
Dana Dachman-Soled, Vitaly Feldman, et al.
SODA 2015