Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-150 | 7th November 2022 23:49

Near-Optimal Derandomization of Medium-Width Branching Programs


Authors: Aaron (Louie) Putterman, Edward Pyne
Publication: 12th November 2022 00:15
Downloads: 183


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)$.

ISSN 1433-8092 | Imprint