Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSEUDORANDOM GENERAORS:
Reports tagged with Pseudorandom generaors:
TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

TR19-149 | 4th November 2019
Dean Doron, Pooya Hatami, William Hoza

#### Log-Seed Pseudorandom Generators via Iterated Restrictions

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>

ISSN 1433-8092 | Imprint