Pseudorandom Generators for Width-3 Branching Programs

Raghu Meka, Omer Reingold, Avishay Tal

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…