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}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.36

Simplifying Armoni’s PRG

Authors: Ben Chen and Amnon Ta-Shma

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

Abstract

We propose a simple variant of the INW pseudo-random generator, where blocks have varying lengths, and prove it gives the same parameters as the more complicated construction of Armoni’s PRG. This shows there is no need for the specialized PRGs of Nisan and Zuckerman and Armoni, and they can be obtained as simple variants of INW. For the construction to work we need space-efficient extractors with tiny entropy loss. We use the extractors from [Chattopadhyay and Liao, 2020] instead of [Guruswami et al., 2009] taking advantage of the very high min-entropy regime we work with. We remark that using these extractors has the additional benefit of making the dependence on the branching program alphabet Σ correct.

Cite as

Ben Chen and Amnon Ta-Shma. Simplifying Armoni’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 36:1-36:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.36,
  author =	{Chen, Ben and Ta-Shma, Amnon},
  title =	{{Simplifying Armoni’s PRG}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{36:1--36:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  URN =		{urn:nbn:de:0030-drops-244024},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.36},
  annote =	{Keywords: PRG, ROBP, read-once, random, psuedorandom, armoni, derandomization}
}

Search Results

Documents authored by Chen, Ben

Improved Error Reduction for Weighted PRGs

Abstract

Cite as

Simplifying Armoni’s PRG

Abstract

Cite as

Thanks for your feedback!

Could not send message