Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudorandom generators for small-space computation:
TR12-083 | 29th June 2012
Thomas Steinke

Pseudorandomness for Permutation Branching Programs Without the Group Theory

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. ... more >>>

TR17-171 | 6th November 2017
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

TR18-112 | 5th June 2018
Raghu Meka, Omer Reingold, Avishay Tal

Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

ISSN 1433-8092 | Imprint