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 a 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\left\{1,\log\log w-\log\log n\right\}}+\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 constructions in Hoza (RANDOM 2022), Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021).Further, by using this result 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).$$ This slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023) and matches the recent simultaneous and independent work of Chen and Ta-shma.

For permutation ROBPs with unbounded widths and single accept nodes, there exists an explicit $\varepsilon$-WPRG with seed length $$ O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$ This slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023).

For regular ROBPs with $n \leq 2^{O(\sqrt{\log w})}, \varepsilon = 1/\text{poly} w$, we give a derandomization within space $O(\log w)$, i.e. in $\mathbf{L}$ exactly.

This is better than previous results of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) in this regime, and we improves the time complexity from super-polynomial to standard polynomial.

Our main method is based on a recursive application of weighted pseudorandom reductions, which is a natural notion that is used to simplify ROBPs.

We corrected a mistake in abstract.

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 a 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\left\{1,\log\log w-\log\log n\right\}}+\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 constructions in Hoza (RANDOM 2022), Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021).Further, by using this result 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).$$ This slightly improves the result of Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021) and matches the recent simultaneous and independent work of Chen and Ta-shma.

For permutation ROBPs with unbounded widths and single accept nodes, there exists an explicit $\varepsilon$-WPRG with seed length $$ O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$ This slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023).

For regular ROBPs with $n \leq 2^{O(\sqrt{\log w})}, \varepsilon = 1/\text{poly} w$, we give a derandomization within space $O(\log w)$, i.e. in $\mathbf{L}$ exactly.

This is better than previous results of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) in this regime, and we improves the time complexity from super-polynomial to standard polynomial.

Our main method is based on a recursive application of weighted pseudorandom reductions, which is a natural notion that is used to simplify ROBPs.

We added some side results, polished writing and removed typos.

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a 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\left\{1,\log\log w-\log\log n\right\}}+\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 constructions in [Hoz21, CDR+21, PV21, CL20]..

For permutation ROBPs with unbounded widths and single accept nodes, there exists an explicit $\varepsilon$-WPRG with seed length
$$ O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$
This slightly improves the result of [CHL+23].

For regular ROBPs with $n \le 2^{O(\sqrt{\log w})}, \varepsilon = 1/\poly w$, we give a derandomization within space $O(\log w)$, i.e. in $\mathbf{L}$ exactly.
This is better than previous results of [AKM+20 , CHL+23 , CL24 ] in this regime.

Our main method is based on a recursive application of weighted pseudorandom reductions, which is a natural notion that is used to simplify ROBPs.