期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-18
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that the Impagliazzo-Nisan-Wigderson [INW94] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of Oe(log d log n · log(1/ε)), assuming the program has only one accepting vertex in the final layer. Here, n is the length of the program, d is the degree (equivalently, the alphabet size), and ε is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length Ω(n log d) to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is “better than random.” Except when the program’s width w is very small, this is an improvement over prior work. For example, when w = poly(n) and d = 2, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nis92], which fools general ordered branching programs with seed length O(log(wn/ε) log n). We prove a seed length lower bound of Ω(log e d log n · log(1/ε)) for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when ε ≤ 1/ log n, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [RV05] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [AKM 20].
