DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.39

Improved Error Reduction for Weighted PRGs

Authors: Ben Chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, and Amnon Ta-Shma

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Ben Chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, and Amnon Ta-Shma. Improved Error Reduction for Weighted PRGs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2026.39,
  author =	{Chen, Ben and Cohen, Gil and Doron, Dean and Khaskelberg, Yuval and Ta-Shma, Amnon},
  title =	{{Improved Error Reduction for Weighted PRGs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.39},
  URN =		{urn:nbn:de:0030-drops-277562},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.39},
  annote =	{Keywords: Space-bounded computation, pseudorandom generators}
}

Search Results

Documents authored by Khaskelberg, Yuval

Improved Error Reduction for Weighted PRGs

Abstract

Cite as

Thanks for your feedback!

Could not send message