ECCC-Report TR22-008https://eccc.weizmann.ac.il/report/2022/008Comments and Revisions published for TR22-008en-usTue, 15 Nov 2022 11:28:11 +0200
Comment 1
| This work has been subsumed |
Gil Cohen
https://eccc.weizmann.ac.il/report/2022/008#comment1This work has been subsumed by the paper "Approximating Iterated Multiplication of Stochastic Matrices in Small Space" (https://eccc.weizmann.ac.il/report/2022/149/).Tue, 15 Nov 2022 11:28:11 +0200https://eccc.weizmann.ac.il/report/2022/008#comment1
Paper TR22-008
| Approximating Large Powers of Stochastic Matrices in Small Space |
Gil Cohen,
Dean Doron,
Ori Sberlo
https://eccc.weizmann.ac.il/report/2022/008We 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$.Fri, 14 Jan 2022 11:34:37 +0200https://eccc.weizmann.ac.il/report/2022/008