ECCC-Report TR22-150https://eccc.weizmann.ac.il/report/2022/150Comments and Revisions published for TR22-150en-usSat, 12 Nov 2022 00:15:04 +0200
Paper TR22-150
| Near-Optimal Derandomization of Medium-Width Branching Programs |
Aaron (Louie) Putterman,
Edward Pyne
https://eccc.weizmann.ac.il/report/2022/150We 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)$.Sat, 12 Nov 2022 00:15:04 +0200https://eccc.weizmann.ac.il/report/2022/150