文章基本信息

标题：Optimal Error Pseudodistributions for Read-Once Branching Programs
本地全文：下载
作者：Eshan Chattopadhyay ; Jyun-Jie Liao
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：25:1-25:27
DOI：10.4230/LIPIcs.CCC.2020.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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â<. log(nw)+log nâ<.log(1/Îµ)) and error Îµ. It remains a central question to reduce the seed length to O(log (nw/Îµ)), which would prove that ððð< = ð<. 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 OÌf(log nâ<. log(nw)+log(1/Îµ)). A PRPD is a relaxation of a pseudorandom generator, which suffices for derandomizing ððð< 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â<. log(nw)+log(1/Îµ)), but their techniques are restricted to hitting sets. In this work, we construct a PRPD with seed length O(log nâ<. log (nw)â<. log log(nw)+log(1/Îµ)). This improves upon the construction by Braverman, Cogen and Garg by a O(log log(1/Îµ)) 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.
关键词：Derandomization; explicit constructions; space-bounded computation