Back to list of papers

Better Pseudodistributions and Derandomization for Space-Bounded Computation

By William M. Hoza

Read the paper: ECCCRANDOM proceedings

Abstract (for specialists)

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 line of work starting with Braverman, Cohen, and Garg (Braverman, Cohen, and Garg SICOMP 2020; Chattopadhyay and Liao CCC 2020; Cohen, Doron, Renard, Sberlo, and Ta-Shma ECCC 2021; Pyne and Vadhan ECCC 2021) has shown how to construct weighted pseudorandom generators (WPRGs, aka pseudorandom pseudodistribution generators) with better seed lengths than Nisan's generator when the error parameter $\varepsilon$ is small.

In this work, we present an explicit WPRG for width-$n$ length-$n$ ROBPs with seed length $O(\log^2 n + \log(1/\varepsilon))$. Our seed length eliminates $\log \log$ factors from prior constructions, and our generator completes this line of research in the sense that further improvements would require beating Nisan's generator in the standard constant-error regime. Our technique is a variation of a recently-discovered reduction that converts moderate-error PRGs into low-error WPRGs (Cohen et al. ECCC 2021; Pyne and Vadhan ECCC 2021). Our version of the reduction uses averaging samplers.

We also point out that as a consequence of the recent work on WPRGs, any randomized space-$S$ decision algorithm can be simulated deterministically in space $O(S^{3/2} / \sqrt{\log S})$. This is a slight improvement over Saks and Zhou's celebrated $O(S^{3/2})$ bound (JCSS 1999). For this application, our improved WPRG is not necessary.

Not-so-abstract (for curious outsiders)

⚠️ This summary might gloss over some important details.

A "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits that "appear random" in some sense. A "weighted pseudorandom generator" is similar, except instead of working with actual probabilities, we work with "pseudoprobabilities," which are allowed to be positive or negative. Pseudoprobability is a little strange, but it turns out that for some purposes, weighted pseudorandom generators are just as useful as ordinary pseudorandom generators — and sometimes they are easier to design. This paper presents a weighted pseudorandom generator whose output can be used in place of truly random bits for any low-memory randomized computation. The generator is a little better than prior work in some cases in terms of the number of coin tosses it makes.

I posted a manuscript online in March 2021; I presented the paper at RANDOM in August 2021; the full version of the paper will appear in the Theory of Computing special issue for RANDOM 2021. The RANDOM proceedings version and the ECCC version are the same except for minor, superficial differences.

Expository material:

Video of my live virtual presentation at RANDOM (August 2021). (Start at 31:00.) Here are the slides from that presentation, and here is the poster I presented at RANDOM.

[Video] My prerecorded presentation for RANDOM (August 2021). Here are the slides from that presentation. See also these longer slides from my Zoom presentation for the Oxford-Warwick Complexity Meetings (July 2021).


An exposition of the paper is included in my PhD dissertation (Chapter 4).


I wrote a survey that discusses the paper (Section 4).

What others think: