Better Pseudodistributions and Derandomization for Space-Bounded Computation

Abstract

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-n length-n read-once branching programs (ROBPs) with error ε and seed length O(log² n + log n ⋅ log(1/ε)) [Nisan, 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 et al., 2020; Chattopadhyay and Liao, 2020; Cohen et al., 2021; Pyne and Vadhan, 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 ε is small.
In this work, we present an explicit WPRG for width-n length-n ROBPs with seed length O(log² n + log(1/ε)). 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., 2021; Pyne and Vadhan, 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} / √{log S}). This is a slight improvement over Saks and Zhou’s celebrated O(S^{3/2}) bound [Saks and Zhou, 1999]. For this application, our improved WPRG is not necessary.