Back to list of papers

# Better Pseudodistributions and Derandomization for Space-Bounded Computation

By William M. Hoza

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: