2026-09-10T09:45:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27756 2026-09-09T12:19:37Z ddc:004 open_access

Improved Error Reduction for Weighted PRGs Chen, Ben Cohen, Gil Doron, Dean Khaskelberg, Yuval Ta-Shma, Amnon Space-bounded computation pseudorandom generators 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 s₀, over any alphabet, into a weighted PRG with seed length s₀ + O(log 1/ε + log log ((log w)/log n)) ⋅ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ben Chen and Gil Cohen and Dean Doron and Yuval Khaskelberg and Amnon Ta-Shma 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.39 urn:nbn:de:0030-drops-277562 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.39 eng https://creativecommons.org/licenses/by/4.0/legalcode