Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs). Denote $n$ and $w$ as the length and the width of an ROBP. We have the following results. For standard ROBPs, there exists an explicit $\varepsilon$-WPRG with seed length $O\left(\frac{\log n \log(nw)}{\max\{1,\log \log w - \log \log n\}} + \log w \left( \log \log \log w - \log \log \max\left\{2,\frac{\log w}{\log n/\varepsilon}\right\} \right) + \log(1/\varepsilon)\right)$. When $n = w^{o(1)}$, this is better than the construction of Hoza (RANDOM 2022), and the construction of Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021). Further, by using this in a black-box way, we attain a WPRG for regular ROBPs with seed length $O\left( \log n \left( \sqrt{\log(1/\varepsilon)} + \log w + \log \log n \right) + \log(1/\varepsilon) \right)$, which slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit $\varepsilon$-WPRG with seed length $O\left( \log n \left( \log \log n + \sqrt{\log(1/\varepsilon)} \right) + \log(1/\varepsilon) \right)$, improving the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). A key difference is that our result implies a WPRG with optimal seed length for short-wide ROBPs with multiple accept nodes. Specifically, after switching to multiple accept nodes in a standard way by replacing $\varepsilon$ with $\varepsilon/w$, this gives a WPRG with optimal seed length $O(\log w)$ for $n = 2^{O(\sqrt{\log w})}$, and error $1/\operatorname{poly} w$. The only previous work attaining optimal seed lengths are Nisan-Zuckerman style PRGs which are only optimal for $n = \operatorname{poly}\log w$, $\varepsilon = 2^{-\log^{0.9} w}$. For regular ROBPs with $n \le 2^{O(\sqrt{\log w})}$, $\varepsilon = 1/\operatorname{poly}(w)$, we give a derandomization within space $O(\log w)$, i.e., in $\mathbf{L}$ exactly. When requiring the derandomization to be in $\mathbf{L}$, the only previous result is again by Nisan-Zuckerman style PRGs, which can only handle $n = \operatorname{poly}\log w$, $\varepsilon = 2^{-\log^{0.9} w}$. If compared to the result of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), then for $n = 2^{O(\sqrt{\log w})}$ our derandomization not only improves the space complexity to optimal, but also substantially improves the time complexity from super-polynomial to standard polynomial in $w$. All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.