TR22-150 Authors: Aaron (Louie) Putterman, Edward Pyne

Publication: 12th November 2022 00:15

Downloads: 748

Keywords:

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space

$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$

In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.

Previously, the best known space complexity for this problem was

$$O\left(\min\{\log n\cdot \log w,\log^{3/2}n+\sqrt{\log n}\cdot \log w\}\right)$$

via the classic algorithms of Savitch (JCSS 1970) and Saks and Zhou (JCSS 1999), which only achieve space $\tilde{O}(\log n)$ for $w=poly\log(n)$.

We prove this result by showing that a variant of the Saks-Zhou algorithm developed by Cohen, Doron, and Sberlo (ECCC 2022) still works without executing one of the steps in the algorithm, the so-called random shift step. This allows us to extend their algorithm from computing the $n$th power of a $w\times w$ stochastic matrix to multiplying $n$ distinct $w\times w$ stochastic matrices with no degradation in space consumption.

In the regime where $w\geq n$, we also show that our approach can achieve parameters matching those of the original Saks-Zhou algorithm (with no loglog factors). Finally, we show that for $w\leq 2^{\sqrt{\log n}}$, an algorithm even simpler than our algorithm and that of Saks and Zhou achieves space $O(\log^{3/2} n)$.