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, we give 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 \frac{n}{\varepsilon}}\right\}\right)+\log\frac{1}{\varepsilon}\right).$$

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). $$

We also give a new Nisan-Zuckerman style derandomization for regular ROBPs with width $w$, length $n = 2^{O(\sqrt{\log w})}$, and multiple accept nodes. We attain optimal space complexity $O(\log w)$ for arbitrary approximation error $\varepsilon = 1/\poly w$.

All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.

We revised our introduction, technical overview, and some proofs to make them clearer for the audience.

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.