Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-008 | 14th January 2022 11:21

Approximating Large Powers of Stochastic Matrices in Small Space

RSS-Feed




TR22-008
Authors: Gil Cohen, Dean Doron, Ori Sberlo
Publication: 14th January 2022 11:34
Downloads: 988
Keywords: 


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 (FOCS'95), that requires $O(\log^{3/2}n + \sqrt{\log n} \cdot \log w)$ space, in the regime $n \gg w$.


Comment(s):

Comment #1 to TR22-008 | 15th November 2022 11:28

This work has been subsumed

Authors: Gil Cohen
Accepted on: 15th November 2022 11:28
Keywords: 


Comment:

This work has been subsumed by the paper "Approximating Iterated Multiplication of Stochastic Matrices in Small Space" (https://eccc.weizmann.ac.il/report/2022/149/).




ISSN 1433-8092 | Imprint