## Pseudorandom Generators for Width-3 Branching Programs

by Raghu Meka, Omer Reingold, and Avishay Tal

#### Oded's comments

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.

#### The original abstract

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.

Back to
list of Oded's choices.