- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Near-Optimal Pseudorandom Generators for Constant-Depth...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas Hoza, William
Description
We give an explicit pseudorandom generator (PRG) for read-once $\mathbf{AC}^0$, i.e., constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-$2$ case (Gopalan et al. FOCS '12). For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\widetilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order (FOCS '18). Looking beyond read-once $\mathbf{AC}^0$, we also show that our PRG fools read-once $\mathbf{AC}^0[\oplus]$ with seed length $\widetilde{O}(t + \log(n/\varepsilon))$, where $t$ is the number of parity gates in the formula. Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions (Advances in Computing Research '89). We assume by recursion that we already have a PRG for depth-$d$ $\mathbf{AC}^0$ formulas. To fool depth-$(d + 1)$ $\mathbf{AC}^0$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\text{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 $\text{polylog} n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal (STOC '19) to fool this simpler formula. Joint work with Dean Doron and Pooya Hatami.
Item Metadata
Title |
Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2019-07-08T13:31
|
Description |
We give an explicit pseudorandom generator (PRG) for read-once $\mathbf{AC}^0$, i.e., constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-$2$ case (Gopalan et al. FOCS '12). For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\widetilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order (FOCS '18). Looking beyond read-once $\mathbf{AC}^0$, we also show that our PRG fools read-once $\mathbf{AC}^0[\oplus]$ with seed length $\widetilde{O}(t + \log(n/\varepsilon))$, where $t$ is the number of parity gates in the formula.
Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions (Advances in Computing Research '89). We assume by recursion that we already have a PRG for depth-$d$ $\mathbf{AC}^0$ formulas. To fool depth-$(d + 1)$ $\mathbf{AC}^0$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\text{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 $\text{polylog} n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal (STOC '19) to fool this simpler formula.
Joint work with Dean Doron and Pooya Hatami.
|
Extent |
48.0 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: UT Austin
|
Series | |
Date Available |
2020-01-05
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0387462
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International