ECCC-Report TR18-112https://eccc.weizmann.ac.il/report/2018/112Comments and Revisions published for TR18-112en-usTue, 12 Jun 2018 00:59:12 +0300
Revision 1
| Pseudorandom Generators for Width-3 Branching Programs |
Raghu Meka,
Omer Reingold,
Avishay Tal
https://eccc.weizmann.ac.il/report/2018/112#revision1We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992].
Our constructions are based on the ``iterated milder restrictions'' approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018].
Two conceptual ideas that play an important role in our analysis are:
(1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier.
(2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions.
In addition, we achieve nearly optimal seed-length $\tilde{O}(\log(n/\epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $\mathrm{poly}\log(n)$ layers.Tue, 12 Jun 2018 00:59:12 +0300https://eccc.weizmann.ac.il/report/2018/112#revision1
Paper TR18-112
| Pseudorandom Generators for Width-3 Branching Programs |
Raghu Meka,
Omer Reingold,
Avishay Tal
https://eccc.weizmann.ac.il/report/2018/112We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992].
Our constructions are based on the ``iterated milder restrictions'' approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018].
Our main technical contributions are:
(1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier.
(2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions.
In addition, we achieve nearly optimal seed-length $\tilde{O}(\log(n/\epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $\mathrm{poly}\log(n)$ layers.Wed, 06 Jun 2018 02:25:01 +0300https://eccc.weizmann.ac.il/report/2018/112