Pseudorandom generators for width-3 branching programs

We construct pseudorandom generators of seed length Õ(log( n )· log(1/є)) that є-fool ordered read-once branching programs (ROBPs) of width 3 and length n . For unordered ROBPs, we construct pseudorandom generators with seed length Õ(log( n ) · poly (1/є)). 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 Õ(log( n /є)) 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 poly log( n ) layers.

Authors

• Raghu Meka
• Omer Reingold
• Avishay Tal

Keywords

• epsilon-biased generator
• pseudorandom generators for small-space computation
• pseudorandom generators for space-bounded computation
• random restrictions
• read once branching programs