Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ZELIN LV:
All reports by Author Zelin Lv:

TR25-050 | 17th April 2025
William Hoza, Zelin Lv

On Sums of INW Pseudorandom Generators

We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies ... more >>>




ISSN 1433-8092 | Imprint