This work makes progress on the wide front of improving over Nisan space-fooling pseudorandom generator (of 1990). The region of the front referred to here is (ordered) constant-width Read Once Branching Program (ROBP), where the point is that Nisan's PRG actually fools general (ordered) ROBP with a seed-length that is the square of the logarithm of their size, whereas their width and length may each be polynomially related to their size. While it was known how to do better in the special case of width two ROBPs, the challenge of handling width three ROBPs attracted much attention in recent years. The current work takes a large step forward on this challenge, obtaining almost optimal PRGs for the case that the desired error is not too small (e.g., constant error or even 1/polylog(n) error).
Section 2 provides a high-level overview of the construction.
We 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.
See ECCC TR18-112.