Hitting sets with near-optimal error for read-once branching programs
Hitting sets with near-optimal error for read-once branching programs
复制标题
对于一次读取分支程序，命中集具有接近最优的错误
DOI：
10.1145/3188745.3188780
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sumegha Garg
中科院分区：
文献类型：
--
作者：
M. Braverman;Gil Cohen;Sumegha Garg
Nisan（CombinatorICA'92）构建了一个长度为n的伪和生成器，宽度n读取式分支程序（ROBPS）具有误差ε和种子长度O（log2n + logn·logn·log（1/ε））。希望将种子长度降低到最佳O（logn+log（1/ε）），或者构建改进的击球集，因为与成功的线相比，它们会产生更强的BPL和RL的降低。在受限制的设置中，对一般，不受限制的机器人没有取得任何进展，Nisan的构造是最好的伪随身杂志，并且在这项工作之前，也是对无限制的机器人的最佳打击。通过构造带有种子长度O的命中术（log2n+log（1/ε））的首个改进。我们的构造严格改善了先前的作品，即log（1/ε）≫ logn，通过使用pseudorandom生成器具有错误ε= 2-（logn（logn 2在他们的BPL⊆l3/2的证明中，我们提出了一项研究计划，以证明BPL⊆l4/3，我们的结果将作为我们的主要技术工具。致电假伪分布。用于取消双面误差算法。
Nisan (Combinatorica’92) constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error ε and seed length O(log2n + logn · log(1/ε)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O(logn+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 O(log2n+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/ε) ≫ logn, is well-motivated by the work of Saks and Zhou (J.CSS’99) who use pseudorandom generators with error ε = 2−(logn)2 in their proof for BPL ⊆ L3/2. We further suggest a research program towards proving that BPL ⊆ L4/3 in which our result achieves one step. As our main technical tool, 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.