Optimal Error Pseudodistributions for Read-Once Branching Programs

Eshan Chattopadhyay, Jyun-Jie Liao

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+…