Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-065 | 21st May 2025 13:55

Simplyfing Armoni's PRG

RSS-Feed




TR25-065
Authors: Amnon Ta-Shma, ben chen
Publication: 21st May 2025 17:43
Downloads: 145
Keywords: 


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 et. al instead of Guruswami et. al 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 $\Sigma$ correct.



ISSN 1433-8092 | Imprint