Pseudorandom Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs

Abstract: Nisan [Nis92] constructed a pseudorandom generator for length n, width n read-once branching programs (ROBPs) with error ε and seed length ~{O}(log2 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 (randomized log-space computation with two-sided error) and RL (randomized log-space computation with one-sided error), 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. Informally, a pseudorandom generator with seed length s specifies 2s paths such that for any length n, width n ROBP, the probability of acceptance (over 2n paths) can be approximated, upto error ε, by the fraction of these 2s paths that are accepting.

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 [SZ99] who use pseudorandom generators with error ε, for length n, width w read-once branching programs, 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, which might be of independent interest. 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. 

Joint work with Mark Braverman and Gil Cohen.

Bio: Sumegha Garg is a graduate student at Princeton University advised by Mark Braverman. She is interested in theoretical Computer Science, particularly in complexity theory, algorithmic fairness, information theory and quantum computing.