Doron, Dean ;
Hatami, Pooya ;
Hoza, William M.
NearOptimal Pseudorandom Generators for ConstantDepth ReadOnce Formulas
Abstract
We give an explicit pseudorandom generator (PRG) for readonce AC^0, i.e., constantdepth readonce formulas over the basis {wedge, vee, neg} with unbounded fanin. The seed length of our PRG is O~(log(n/epsilon)). Previously, PRGs with nearoptimal seed length were known only for the depth2 case [Gopalan et al., 2012]. For a constant depth d > 2, the best prior PRG is a recent construction by Forbes and Kelley with seed length O~(log^2 n + log n log(1/epsilon)) for the more general model of constantwidth readonce branching programs with arbitrary variable order [Michael A. Forbes and Zander Kelley, 2018]. Looking beyond readonce AC^0, we also show that our PRG fools readonce AC^0[oplus] with seed length O~(t + log(n/epsilon)), where t is the number of parity gates in the formula.
Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions [Ajtai and Wigderson, 1989]. We assume by recursion that we already have a PRG for depthd AC^0 formulas. To fool depth(d + 1) AC^0 formulas, we use the given PRG, combined with a smallbias distribution and almost kwise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley [Michael A. Forbes and Zander Kelley, 2018] shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after poly(log log n) independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only polylog n remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal [Meka et al., 2019] to fool this simpler formula.
BibTeX  Entry
@InProceedings{doron_et_al:LIPIcs:2019:10838,
author = {Dean Doron and Pooya Hatami and William M. Hoza},
title = {{NearOptimal Pseudorandom Generators for ConstantDepth ReadOnce Formulas}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {16:116:34},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10838},
URN = {urn:nbn:de:0030drops108382},
doi = {10.4230/LIPIcs.CCC.2019.16},
annote = {Keywords: Pseudorandom generators, Constantdepth formulas, Explicit constructions}
}
2019
Keywords: 

Pseudorandom generators, Constantdepth formulas, Explicit constructions 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 