Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity as it constitutes the main route towards resolving the BPL vs. L problem. The seminal work by Saks and Zhou [JCSS ’99] gives a deterministic algorithm for approximating the product of n stochastic matrices of dimension w × w in space O(log3/2n + √logn · logw). The first improvement upon Saks–Zhou was achieved by Hoza [RANDOM ’21] who gave a logarithmic improvement in the n=poly(w) regime, attaining O(1/√loglogn · log3/2n) space.