Recursive Error Reduction for Regular Branching Programs

Recursive Error Reduction for Regular Branching Programs (via Zoom)

Abstract: Proving whether BPL can be derandomized in log space is a long-standing open problem in complexity theory, and a natural approach to prove this conjecture is to construct a pseudorandom generator (PRGs) for read-once branching programs (ROBPs). Despite decades of effort, the state-of-the-art PRG construction is still Nisan's PRG that was constructed in the 90s. Nevertheless, an exciting work by Braverman, Cohen and Garg in STOC 2018 showed how to get a better seed length than Nisan's PRG when we consider a relaxed "weighted PRG" (WPRG) notion instead. A subsequent line of works on WPRG culminated in a result by Hoza in RANDOM 2021 which achieved the first improvement over a two-decade-old bound by Saks and Zhou on derandomizing BPL. 
While Nisan's PRG remains unbeatable in the general setting, there were some nice results on getting better seed lengths in restricted settings of ROBPs, and it is natural to ask whether one can apply the new WPRG techniques to obtain better WPRG in the restricted settings. A nice result by Chen, Hoza, Lyu, Tal and Wu in FOCS 2023 solved this task, but the analysis was tricky. In this work we show a simpler proof based on a "recursive error reduction framework".

Bio: Jyun-Jie is a 6th year PhD student in Cornell CIS, advised by Eshan Chattopadhyay. He is broadly interested in complexity, cryptography and combinatorics, with a main research focus on pseudorandomness.