License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.25
URN: urn:nbn:de:0030-drops-125779
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12577/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Eshan ; Liao, Jyun-Jie

Optimal Error Pseudodistributions for Read-Once Branching Programs

pdf-format:
LIPIcs-CCC-2020-25.pdf (0.6 MB)

Abstract

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 Õ(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.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2020:12577,
  author =	{Eshan Chattopadhyay and Jyun-Jie Liao},
  title =	{{Optimal Error Pseudodistributions for Read-Once Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{25:1--25:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12577},
  URN =		{urn:nbn:de:0030-drops-125779},
  doi =		{10.4230/LIPIcs.CCC.2020.25},
  annote =	{Keywords: Derandomization, explicit constructions, space-bounded computation}
}

Keywords: Derandomization, explicit constructions, space-bounded computation
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI