论文标题
用于读取对接分支程序的最佳错误假越差
Optimal Error Pseudodistributions for Read-Once Branching Programs
论文作者
论文摘要
In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$.将种子长度减少到$ o（\ log（nw/\ varepsilon））$仍然是一个核心问题，这将证明$ \ mathbf {bpl} = \ mathbf {l} $。但是，Nisan的构建$ n = W $没有改善，这与空间结合的derandomization最相关。 最近，在一件精美的作品中，布拉弗曼，科恩和加尔格（stoc'18）介绍了伪随机伪分发（PRPD）的概念，并明确地构造了带有种子长度$ \ tilde $ \ tilde {o}（\ log n \ log n \ cdot \ cdot \ cdot \ log \ log（nw）$ \ log的prpd的构建。 PRPD是伪随机生成器的放松，足以使$ \ mathbf {bpl} $降低，这也意味着击中集合。不幸的是，他们的构建非常参与和复杂。 Hoza和Zuckerman（focs'18）随后构建了一个更简单的命中式发电机，带有种子长度$ O（\ log n \ cdot \ log（nw）+\ log（1/\ varepsilon））$，但其技术仅限于击打集。 在这项工作中，我们构造了一个具有种子长度$$ o（\ log n \ cdot \ log（nw）\ cdot \ log \ log \ log \ log（nw）+\ log（1/\ varepsilon））的PRPD。此外，我们认为我们的构建和分析比Braverman，Cohen和Garg的工作更简单。
In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has been no improvement on Nisan's construction for the case $n=w$, which is most relevant to space-bounded derandomization. Recently, in a beautiful work, Braverman, Cohen and Garg (STOC'18) introduced the notion of a pseudorandom pseudo-distribution (PRPD) and gave an explicit construction of a PRPD with seed length $\tilde{O}(\log n\cdot \log(nw)+\log(1/\varepsilon))$. A PRPD is a relaxation of a pseudorandom generator, which suffices for derandomizing $\mathbf{BPL}$ and also implies a hitting set. Unfortunately, their construction is quite involved and complicated. Hoza and Zuckerman (FOCS'18) later constructed a much simpler hitting set generator with seed length $O(\log n\cdot \log(nw)+\log(1/\varepsilon))$, but their techniques are restricted to hitting sets. In this work, we construct a PRPD with seed length $$O(\log n\cdot \log (nw)\cdot \log\log(nw)+\log(1/\varepsilon)).$$ This improves upon the construction in [BCG18] by a $O(\log\log(1/\varepsilon))$ factor, and is optimal in the small error regime. In addition, we believe our construction and analysis to be simpler than the work of Braverman, Cohen and Garg.
