This work reports another step in the research journey towards better derandomization of space-bounded randomized computation, where prior recent steps were recommended by me in postings number 283 and 299. Again, favorite themes such as first obtaining a mild approximation and then improving it (via the Richardson iteration) play a pivotal role.* In addition, the paper provides an exceptionally nice exposition, which seems accessible also to non-experts.
*)
I view this as a special case of the
ZigZag Method.
We give a deterministic space-efficient algorithm
for approximating powers of stochastic matrices.
On input a $w \times w$ stochastic matrix $A$,
our algorithm approximates $A^{n}$
in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$
to within high accuracy.
This improves upon the seminal work by Saks and Zhou (FOCS95),
that requires $O(\log^{3/2}n + \sqrt{\log n} \cdot \log w)$ space,
in the regime $n \gg w$.
Available from
ECCC TR22-008.
The original abstract
Back to
list of Oded's choices.