## Approximating Large Powers of Stochastic Matrices in Small Space

by Gil Cohen, Dean Doron, and Ori Sberlo

#### Oded's comments

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.
}

**Update (by Ted Pyne, 17-Nov-22):**
This work was recently superseded by a pair of papers,
ECCC TR22-149
and ECCC TR22-150,
which obtain near-optimal complexity for iterated matrix multiplication
(whereas the prior result held for powering a single matrix):
Interestingly, although the final result is the same,
the ideas used to go beyond the single-matrix case
are totally different.

#### The original abstract

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.

Back to
list of Oded's choices.