Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-161 | 30th April 2020 21:02

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

RSS-Feed




Revision #1
Authors: Mark Braverman, Gil Cohen, Sumegha Garg
Accepted on: 30th April 2020 21:02
Downloads: 931
Keywords: 


Abstract:

Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2{n} + \log{n} \cdot \log(1/\varepsilon))$. A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal $O(\log{n}+\log(1/\varepsilon))$, or to construct improved hitting sets, as these would yield stronger derandomization of $\mathbf{BPL}$ and $\mathbf{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 $\widetilde{O}(\log^2{n}+\log(1/\varepsilon))$. That is, we decouple $\varepsilon$ 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/\varepsilon) \gg \log{n}$, is also motivated by the work of Saks and Zhou (J.CSS'99) who use pseudorandom generators with error $\varepsilon$, for length $n$, width $w$ read-once branching programs, such that $w,1/\varepsilon = 2^{(\log{n})^{2}}$ in their proof for $\mathbf{BPL} \subseteq \mathbf{L}^{3/2}$.

In fact, we introduce and construct a new type of primitive we call \emph{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.



Changes to previous version:

Minor changes to the writing, fixing typos and added more description for the constructed pseudo-PRG.


Paper:

TR17-161 | 30th October 2017 20:07

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs


Abstract:

Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2{n} + \log{n} \cdot \log(1/\varepsilon))$. A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal $O(\log{n}+\log(1/\varepsilon))$, or to construct improved hitting sets, as these would yield stronger derandomization of $\mathbf{BPL}$ and $\mathbf{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 $\widetilde{O}(\log^2{n}+\log(1/\varepsilon))$. That is, we decouple $\varepsilon$ 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/\varepsilon) \gg \log{n}$, is well-motivated by the work of Saks and Zhou (J.CSS'99) who use pseudorandom generators with error $\varepsilon = 2^{-(\log{n})^{2}}$ in their proof for $\mathbf{BPL} \subseteq \mathbf{L}^{3/2}$. We further suggest a research program towards proving that $\mathbf{BPL} \subseteq \mathbf{L}^{4/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.



ISSN 1433-8092 | Imprint