2026-07-24T17:52:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12577 2024-03-06T10:50:29Z ddc:004 open_access

Optimal Error Pseudodistributions for Read-Once Branching Programs Chattopadhyay, Eshan Liao, Jyun-Jie Derandomization explicit constructions space-bounded computation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eshan Chattopadhyay and Jyun-Jie Liao 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.25 urn:nbn:de:0030-drops-125779 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.25 eng https://creativecommons.org/licenses/by/3.0/legalcode