Jyun-Jie Liao (Theory Seminar)

Whether BPL equals L is a long-standing open problem in complexity theory, and a natural approach toward proving this conjecture is to construct a pseudorandom generator (PRG) for read-once branching programs (ROBP). Despite decades of efforts, the best known PRG for ROBP is still Nisan's construction in the 90s. Nevertheless, Braverman, Cohen and Garg introduced a relaxed notion called weighted PRG (WPRG), and showed how to construct WPRG with better seed length than Nisan's PRG in the small error regime. This concept stimulated a fruitful line of works, including Hoza's improved derandomization for BPL. More recently, Chen, Hoza, Lyu, Tal and Wu showed how to construct WPRGs with even better seed length in an interesting special case: regular branching programs. Their work clearly demonstrates how regularity can be useful in WPRG construction, but their analysis is somewhat involved. In this work, we show how to obtain the same result using an alternative construction with very simple analysis.