Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR20-069 | 3rd June 2020 03:57

#### Optimal Error Pseudodistributions for Read-Once Branching Programs

Revision #1
Accepted on: 3rd June 2020 03:57
Keywords:

Abstract:

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\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error
$\varepsilon$. It remains a central question to reduce the seed length to
$O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$.
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 $\tilde{O}(\log n\cdot \log(nw)+\log(1/\varepsilon))$. A PRPD is a relaxation of a pseudorandom
generator, which suffices for derandomizing $\mathbf{BPL}$ 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\cdot \log(nw)+\log(1/\varepsilon))$, but their techniques are restricted to hitting
sets.
In this work, we construct a PRPD with seed length $$O(\log n\cdot \log (nw)\cdot \log\log(nw)+\log(1/\varepsilon)).$$ This improves upon the
construction in [BCG18] by a $O(\log\log(1/\varepsilon))$ 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.

Changes to previous version:

added details about using the Saks-Zhou scheme with PRPDs (Appendix A). Other minor changes.

### Paper:

TR20-069 | 4th May 2020 00:34

#### Optimal Error Pseudodistributions for Read-Once Branching Programs

TR20-069
Publication: 4th May 2020 01:01
Keywords:

Abstract:

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\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. 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 \emph{pseudorandom pseudo-distribution} (PRPD) and gave an explicit construction of a PRPD with seed length $\tilde{O}(\log n\cdot \log(nw)+\log(1/\varepsilon))$. A PRPD is a relaxation of a pseudorandom generator, which suffices for derandomizing $\mathbf{BPL}$ 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\cdot \log(nw)+\log(1/\varepsilon))$, but their techniques are restricted to hitting sets.

In this work, we construct a PRPD with seed length
$$O(\log n\cdot \log (nw)\cdot \log\log(nw)+\log(1/\varepsilon)).$$
This improves upon the construction in \cite{BCG18} by a $O(\log\log(1/\varepsilon))$ 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.

ISSN 1433-8092 | Imprint