TY - JOUR

T1 - Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs

AU - BRAVERMAN, MARK

AU - COHEN, GIL

AU - GARG, SUMEGHA

N1 - Funding Information:
\ast Received by the editors July 2, 2018; accepted for publication (in revised form) December 4, 2019; published electronically February 18, 2020. https://doi.org/10.1137/18M1197734 Funding: The first author's research was supported in part by NSF awards DMS-1128155, CCF-1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. \dagger Department of Computer Science, Princeton University, Princeton, NJ 08540 (mbraverm@cs. princeton.edu). Part of this work was done while this author was a Fellow at the Institute for Advanced Study. \ddagger School of Computer Science, Tel Aviv University, Tel-Aviv, 69978, Israel (coheng@gmail.com). This work was done while this author was a postdoctoral researcher at Princeton University. \S Department of Computer Science, Princeton University, Princeton, NJ 08540 (sumeghag@cs. princeton.edu).
Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - Nisan [Combinatorica, 12 (1992), pp. 449-461] 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 also motivated by the work of Saks and Zhou [J. Comput. System Sci., 58 (1999), pp. 376-403], who use pseudorandom generators with error , for length n, width w ROBPs, such that w, 1/ = 2(log n)2 in their proof for BPL ⊆ L3/2. In fact, 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.

AB - Nisan [Combinatorica, 12 (1992), pp. 449-461] 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 also motivated by the work of Saks and Zhou [J. Comput. System Sci., 58 (1999), pp. 376-403], who use pseudorandom generators with error , for length n, width w ROBPs, such that w, 1/ = 2(log n)2 in their proof for BPL ⊆ L3/2. In fact, 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.

KW - Derandomization

KW - Hitting sets

KW - Read-once branching programs

KW - Space-bounded computation

UR - http://www.scopus.com/inward/record.url?scp=85089392004&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089392004&partnerID=8YFLogxK

U2 - 10.1137/18M1197734

DO - 10.1137/18M1197734

M3 - Article

AN - SCOPUS:85089392004

VL - 49

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 5

ER -