首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Optimal Error Pseudodistributions for Read-Once Branching Programs
  • 本地全文:下载
  • 作者:Eshan Chattopadhyay ; Jyun-Jie Liao
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2020
  • 卷号:2020
  • 页码:1-25
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要: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 BPL = 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 O˜(log n · log(nw) log(1/ε)). A PRPD is a relaxation of a pseudorandom generator, which suffices for derandomizing 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 · 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 in [BCG18] 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.
国家哲学社会科学文献中心版权所有