文章基本信息

标题：Better Pseudodistributions and Derandomization for Space-Bounded Computation
本地全文：下载
作者：William Hoza
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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(log2n+lognlog(1)) (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 is small. In this work, we present an explicit WPRG for width-n length-n ROBPs with seed length O(log2n+log(1)) . Our seed length eliminates loglog 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(S32logS) . This is a slight improvement over Saks and Zhou's celebrated O(S32) bound (JCSS 1999). For this application, our improved WPRG is not necessary.