Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Space-bounded Derandomization:
TR13-086 | 13th June 2013
Omer Reingold, Thomas Steinke, Salil Vadhan

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

TR21-048 | 27th March 2021
William Hoza

Better Pseudodistributions and Derandomization for Space-Bounded Computation

Revisions: 1

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-$n$ length-$n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2 n + \log n \cdot \log(1/\varepsilon))$ (Combinatorica 1992). Nisan's generator remains the best explicit PRG known for this important model of computation. However, a recent ... more >>>

TR21-108 | 22nd July 2021
Edward Pyne, Salil Vadhan

Limitations of the Impagliazzo--Nisan--Wigderson Pseudorandom Generator against Permutation Branching Programs

The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the ... more >>>

ISSN 1433-8092 | Imprint