Optimal Error Pseudodistributions for Read-Once Branching Programs

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)+\log n\cdot \log (1\mathrm{/}\epsilon ))$ and error $\epsilon$. It remains a central question to reduce the seed length to $O(\log (nw\mathrm{/}\epsilon ))$, which would prove that $\mathbf{B}\mathbf{P}\mathbf{L}=\mathbf{L}$. However, there has been no improvement on Nisan’s construction for the case $n=w$, which is most relevant to space-bounded derandomization. Recently, in a beautiful work, Braverman, Cohen and Garg (STOC’18) introduced the notion of a pseudorandom pseudo-distribution (PRPD) and gave an explicit construction of a PRPD with seed length $\tilde{O}(\log n\cdot \log(nw)+\log(1/\varepsilon))$. A PRPD is a relaxation of a pseudorandom generator, which suffices for derandomizing $\mathbf{B}\mathbf{P}\mathbf{L}$ and also implies a hitting set. Unfortunately, their construction is quite involved and complicated. Hoza and Zuckerman (FOCS’18) later constructed a much simpler hitting set generator with seed length $O(\log n\cdot \log(nw)+\log(1/\varepsilon))$, but their techniques are restricted to hitting sets. In this work, we construct a PRPD with seed length $$O(\log n\cdot \log (nw)\cdot \log \log (nw)+\log (1\mathrm{/}\epsilon ))\mathrm{.}$$ This improves upon the construction in [BCG18] by a $O(\log \log (1\mathrm{/}\epsilon ))$ factor, and is optimal in the small error regime. In addition, we believe our construction and analysis to be simpler than the work of Braverman, Cohen and Garg.