Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BEN CHEN:
All reports by Author ben chen:

TR25-067 | 21st May 2025
Amnon Ta-Shma, ben chen

Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs

In this work, we combine the work of Chen et. al and Hoza to obtain a WPRG against regular ROBPs
with seed length $O(\log t \cdot (\log w+\sqrt{\log \frac{1}{\epsilon}}+\log\log t) + \log \frac {1}{\epsilon})$, improving
upon previous construction which also include some additional lower order terms.

more >>>

TR25-065 | 21st May 2025
Amnon Ta-Shma, ben chen

Simplyfing Armoni's PRG

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 ... more >>>




ISSN 1433-8092 | Imprint