2026-08-16T23:36:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24402 2025-12-12T15:01:31Z ddc:004 open_access

Simplifying Armoni’s PRG Chen, Ben Ta-Shma, Amnon PRG ROBP read-once random psuedorandom armoni derandomization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ben Chen and Amnon Ta-Shma 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.36 urn:nbn:de:0030-drops-244024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode