We devise an error-reduction procedure that transforms a PRG for length-$n$, width-$w$ read-once branching programs with error $1/\mathrm{poly}(n)$ and seed length $s_0$ into a weighted PRG with seed length
$$
s_0 + O\left( \log \frac{1}{\varepsilon} + \log\log\left( \frac{\log w}{\log n} \right)\cdot \log w \right).
$$
Using this reduction, we improve upon the state-of-the-art weighted PRG constructions of Hoza (RANDOM 2021) and Cheng and Wu (SODA 2026), achieving optimal dependence on the program's arity while matching the best known bounds in all other parameters.

Our motivation for obtaining optimal dependence on the arity stems from a result of Cheng and Hoza (CCC 2020, ToC 2022), who showed that a PRG with optimal arity and error dependence yields a PRG with seed length $O(\log^{3/2} n)$ (for, say, constant width), thereby breaking the long-standing log-squared barrier.

Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction.

We show that breaking this barrier, even achieving seed length $O(\log^{3/2} n)$ (for, say, constant width), would follow from simultaneously improving the dependence of PRGs on two seemingly secondary parameters: the error $\varepsilon$ and the program's arity $|\Sigma|$. Such improved dependence is already achieved by certain weighted PRGs (WPRGs). This reduces the problem of breaking the log-squared barrier to deweightization: closing the gap between PRG and WPRG constructions.

While the importance of the error parameter has been recognized over the past decade, the role of the arity $|\Sigma|$ has largely been overlooked. By inspection, several existing WPRG constructions achieve optimal dependence on $\Sigma$, though the state-of-the-art constructions do not. As our second result, we construct WPRGs that attain optimal dependence on $\Sigma$ while matching the best known bounds in all other parameters.

We devise an error-reduction procedure that transforms a PRG for length-$n$, width-$w$ read-once branching programs with error $1/\mathrm{poly}(n)$ and seed length $s_0$ into a weighted PRG with seed length
$$
s_0 + O\left( \log \frac{1}{\varepsilon} + \log\log\left( \frac{\log w}{\log n} \right)\cdot \log w \right).
$$
Using this reduction, we improve upon the state-of-the-art weighted PRG constructions of Hoza (RANDOM 2021) and Cheng and Wu (SODA 2026), achieving optimal dependence on the program's arity while matching the best known bounds in all other parameters.

Our motivation for obtaining optimal dependence on the arity stems from a result of Cheng and Hoza (CCC 2020, ToC 2022), who showed that a PRG with optimal arity and error dependence yields a PRG with seed length $O(\log^{3/2} n)$ (for, say, constant width), thereby breaking the long-standing log-squared barrier.

Theorem 1.1 of the previous version is now correctly attributed to Cheng and Hoza.

Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction.

We show that breaking this barrier, even achieving seed length $O(\log^{3/2} n)$ (for, say, constant width), would follow from simultaneously improving the dependence of PRGs on two seemingly secondary parameters: the error $\varepsilon$ and the program's arity $|\Sigma|$. Such improved dependence is already achieved by certain weighted PRGs (WPRGs). This reduces the problem of breaking the log-squared barrier to deweightization: closing the gap between PRG and WPRG constructions.

While the importance of the error parameter has been recognized over the past decade, the role of the arity $|\Sigma|$ has largely been overlooked. By inspection, several existing WPRG constructions achieve optimal dependence on $\Sigma$, though the state-of-the-art constructions do not. As our second result, we construct WPRGs that attain optimal dependence on $\Sigma$ while matching the best known bounds in all other parameters.