ECCC-Report TR21-048https://eccc.weizmann.ac.il/report/2021/048Comments and Revisions published for TR21-048en-usSat, 27 Mar 2021 11:27:49 +0300
Paper TR21-048
| Better Pseudodistributions and Derandomization for Space-Bounded Computation |
William Hoza
https://eccc.weizmann.ac.il/report/2021/048Three 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.Sat, 27 Mar 2021 11:27:49 +0300https://eccc.weizmann.ac.il/report/2021/048