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

TR26-243 | 10th October 2026
Gil Cohen

Fooling Low-Degree Polynomials: PRGs with Optimal Dependence on Input Length and Expander Walks

In a recent breakthrough, Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola (ECCC'26) established exponential correlation bounds for polynomials over $\mathbf{F}_2$ and, as a consequence, obtained a major improvement in PRG constructions for low-degree polynomials over the binary field. In particular, they obtained seed length $\widetilde{O}(d^2\log^2 n)$ for fooling degree-$d$ polynomials ... more >>>


TR26-302 | 3rd November 2026
Oliver Korten

Tight Depth Lower Bounds for Stretch Amplification

We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box ... more >>>




ISSN 1433-8092 | Imprint