Nisan [Nis92] constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error ε and seed length O(log^2(n) + log(n) · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O(log(n) + log(1/ε)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL, respectively. In this talk, we make the first improvement by constructing a hitting set with seed length ~O����(log^2(n) + log(1/ε)). That is, we decouple ε and n, and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, log(1/ε) ≫ log n, is well- motivated by the work of Saks and Zhou [SZ99] who use pseudorandom generators with error ε = 2^{−log^2(n)} in their proof for BPL ⊆ L^{3/2}.

Joint work with Mark Braverman and Gil Cohen.