\(\renewcommand{\epsilon}{\varepsilon}\) \(\renewcommand{\hat}{\widehat}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\)

Back to list of papers


Better Pseudodistributions and Derandomization for Space-Bounded Computation

By William M. Hoza


Read the paper: ECCC

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 \(\epsilon\) and seed length \(O(\log^2 n + \log n \cdot \log(1/\epsilon))\) (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 \(\epsilon\) 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/\epsilon))\). 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 negative or bigger than 1. 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.

Manuscript posted online in March 2021.


What others think: