Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
复制标题
一次性读取分支程序的具有近最优误差的伪随机伪分布
DOI：
10.1137/18m1197734
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Sumegha Garg
中科院分区：
文献类型：
--
作者：
M. Braverman;Gil Cohen;Sumegha Garg
Nisan [Nis92]构造了一个伪随机生成器，用于长度为n，宽度为n，误差为ε，种子长度为O （log 2n + log n·log(1 /ε)）的只读一次分支程序（robp）。复杂性理论的一个主要目标是将种子长度减少到最优的O (log n +log(1 /ε))，或者构建改进的命中集，因为这些将分别产生更强的BPL和RL的非随机化。与限制环境下的成功工作相比，一般的、不受限制的robp没有取得任何进展。事实上，Nisan的构造是最好的伪随机生成器，在此工作之前，也是无限制robp的最佳命中集。在这项工作中，我们通过构造一个种子长度为（cid:101） O （log 2n + log(1 /ε)）的命中集，对一般情况进行了第一次改进。也就是说，我们解耦了ε和n，并获得了对前者的近似最优依赖。Saks和Zhou [SZ99]对长度n，宽度w的一次读分支程序使用了误差为ε的伪随机生成器，使得在BPL的3 / 2的证明中，w, 1 /ε = 2 (log n) 2。我们的构造严格改进了先前工作的参数体系，即log（1 /ε) (cid:29) log n）。实际上，我们引入并构造了一种新的基元，我们称之为伪随机伪分布。非正式地说，这是伪随机生成器的泛化，其中可以为路径分配负的无界权重，而不是使用概率分布。我们证明了这样的原语产生命中集，并且对于非随机化的目的，可以用于非随机化双边误差算法。
Nisan [Nis92] constructed a pseudorandom generator for length n , width n read-once branching programs (ROBPs) with error ε and seed length O (log 2 n + log n · log(1 /ε )). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O (log n +log(1 /ε )), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL , respectively. In contrast to a successful line of work in restricted settings, no progress has been made for general, unrestricted, ROBPs. Indeed, Nisan’s construction is the best pseudorandom generator and, prior to this work, also the best hitting set for unrestricted ROBPs. In this work, we make the first improvement for the general case by constructing a hitting set with seed length (cid:101) O (log 2 n + log(1 /ε )). That is, we decouple ε and n , and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, log(1 /ε ) (cid:29) log n , is also motivated by the work of Saks and Zhou [SZ99] who use pseudorandom generators with error ε , for length n , width w read-once branching programs, such that w, 1 /ε = 2 (log n ) 2 in their proof for BPL ⊆ L 3 / 2 . In fact, we introduce and construct a new type of primitive we call pseudorandom pseudo-distributions . Informally, this is a generalization of pseudorandom generators in which one may assign negative and unbounded weights to paths as opposed to working with probability distributions. We show that such a primitive yields hitting sets and, for derandomization purposes, can be used to derandomize two-sided error algorithms.