Near-Optimal Derandomization of Medium-Width Branching Programs

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 Õ(logn+√logn·logw). In particular, we obtain an almost optimal space Õ(logn) derandomization of programs up to width w=2√logn. Previously, the best known space complexity for this problem was O(minlogn· logw,log3/2n+√logn· logw) via the classic algorithms of Savitch (JCSS 1970) and Saks and Zhou (JCSS 1999), which only achieve space Õ(logn) for w=polylog(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 nth power of a w× w stochastic matrix to multiplying n distinct w× w stochastic matrices with no degradation in space consumption. In the regime where w≥ 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≤ 2√logn, an algorithm even simpler than our algorithm and that of Saks and Zhou achieves space O(log3/2 n).