Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PRG:
Reports tagged with PRG:
TR20-018 | 18th February 2020
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... 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 >>>


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



ISSN 1433-8092 | Imprint