Better Pseudodistributions and Derandomization for Space-Bounded Computation
Better Pseudodistributions and Derandomization for Space-Bounded Computation
复制标题
更好的空间有限计算的伪分布和去随机化
DOI：
--
复制
发表时间：
2021
影响因子：
4.1
通讯作者：
William M. Hoza
中科院分区：
文献类型：
--
作者：
William M. Hoza
三十年前，Nisan构建了一个显式的伪和生成器（PRG），该发电机（PRG）愚弄了width-n Length-n read-n-Once分支程序（ROBPS），具有错误ε和种子长度O（log 2 n + log n log n·log（1 /ε） [NIS92]。伪随机生成器（WPRG，又称伪dododododistribution Generator）比Nisan的生成器更好的种子长度时，当误差参数ε在这项工作中很小，我们提出了带有种子长度O的width-n Length-N长度O（log 2 N）的显式WPRG +日志（1 /ε）。我们的种子长度从先前的构造中消除了日志因素，而我们的发电机则完成了这一研究，即进一步的改进将需要在标准的恒定率上击败Nisan的发电机最近发现的降低的变体将中等率的PRG转换为低误差WPRG [CDRSTS21]。随机Space-S决策算法可以在空间O（CID：0）S 3/2 /√LOGS（CID：1）中进行确定性模拟。 [SZ99]。
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 2 n + log n · log(1 /ε )) [Nis92]. 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 [BCG20; CL20; CDRSTS21; PV21] 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 2 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 [CDRSTS21; PV21]. 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 (cid:0) S 3 / 2 / √ log S (cid:1) . This is a slight improvement over Saks and Zhou’s celebrated O ( S 3 / 2 ) bound [SZ99]. For this application, our improved WPRG is not necessary.
小空间随机游走的高精度估计
DOI：
10.1109/focs46700.2020.00123
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Ahmadinejad, AmirMahdi;Kelner, Jonathan;Murtagh, Jack;Peebles, John;Sidford, Aaron;Vadhan, Salil
通讯作者：
Vadhan, Salil
小成功 RL 的简单最佳击球组合
影响因子：
1.6
作者：
Hoza, William M.;Zuckerman, David
通讯作者：
Zuckerman, David