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.