דין דורון

We devise an error-reduction procedure that transforms a PRG for length-n, width-w read-once branching programs with error 1/poly(n) and seed length s0, over any alphabet, into a weighted PRG with seed length s0 + O (log 1/ε + log log (log w/logn) · log w). 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.