Hitting sets with near-Optimal error for read-Once branching programs

Mark Braverman, Gil Cohen, Sumegha Garg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Nisan (Combinatorica’92) constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error and seed length O(log2 n + log n · log(1/)). A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal O(log n + log(1/)), or to construct improved hitting sets, as these would yield stronger derandomization of BPL and RL, respectively. In contrast to a successful line of work in restricted settings, no progress has been made for general, unrestricted, ROBPs. Indeed, Nisan’s construction is the best pseudorandom generator and, prior to this work, also the best hitting set for unrestricted ROBPs. In this work, we make the first improvement for the general case by constructing a hitting set with seed length O(log2 n + log(1/)). That is, we decouple and n, and obtain near-optimal dependence on the former. The regime of parameters in which our construction strictly improves upon prior works, namely, log(1/) ≫ log n, is well-motivated by the work of Saks and Zhou (J.CSS’99) who use pseudorandom generators with error = 2−(log n)2 in their proof for BPL ⊆ L3/2. We further suggest a research program towards proving that BPL ⊆ L4/3 in which our result achieves one step. As our main technical tool, we introduce and construct a new type of primitive we call pseudorandom pseudo-distributions. Informally, this is a generalization of pseudorandom generators in which one May assign negative and unbounded weights to paths as opposed to working with probability distributions. We show that such a primitive yields hitting sets and, for derandomization purposes, can be used to derandomize two-sided error algorithms.

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages940-951
Number of pages12
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period6/25/186/29/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Derandomization
  • Hitting sets
  • Read once branching programs
  • Space-bounded computation

Fingerprint Dive into the research topics of 'Hitting sets with near-Optimal error for read-Once branching programs'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Cohen, G., & Garg, S. (2018). Hitting sets with near-Optimal error for read-Once branching programs. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 940-951). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188780