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.

In this talk, we give the first polynomial improvement over the seminal work by Saks and Zhou (1999), who gave a deterministic algorithm for approximating the product of n stochastic matrices of dimension w×w in space O(log3/2n+ (log n)1/2·log w). Our algorithm achieves space complexity of O~(log n+ (log n)1/2·log w), which outperforms [SZ99] whenever n greater than w. In particular, in the regime log n greater than log2w, our algorithm runs in nearly-optimal O~(log n) space, improving upon the previous best O(log3/2n).

Joint work with Gil Cohen, Ori Sberlo, and Amnon Ta-Shma.