High-precision Estimation of Random Walks in Small Space
© 2020 IEEE. In this paper, we provide a deterministic tilde{O}(log N)-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error (epsilon=1 text{poly}(N)) where N is the length of the input....
| Egile Nagusiak: | , , , , , |
|---|---|
| Beste egile batzuk: | |
| Formatua: | Artikulua |
| Hizkuntza: | English |
| Argitaratua: |
IEEE
2021
|
| Sarrera elektronikoa: | https://hdl.handle.net/1721.1/137303 |
| _version_ | 1826217750332178432 |
|---|---|
| author | Ahmadinejad, AmirMahdi Kelner, Jonathan Murtagh, Jack Peebles, John Sidford, Aaron Vadhan, Salil |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ahmadinejad, AmirMahdi Kelner, Jonathan Murtagh, Jack Peebles, John Sidford, Aaron Vadhan, Salil |
| author_sort | Ahmadinejad, AmirMahdi |
| collection | MIT |
| description | © 2020 IEEE. In this paper, we provide a deterministic tilde{O}(log N)-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error (epsilon=1 text{poly}(N)) where N is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space O(log N) (following Aleliunas et al., FOCS'79) and by a deterministic algorithm using space O(log{3/2}N) (Saks and Zhou, FOCS'95 and JCSS'99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible (epsilon=1/N{omega(1)}), generalizing what Hoza and Zuckerman (FOCS'18) recently showed for the special case of distinguishing whether a random walk probability is 0 or greater than epsilon. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic tilde{O}(log N)-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS'17) that gave a deterministic tilde{O}(log N)-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS'19) that gave a randomized tilde{O}(N)-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of'cycle-lifted graphs,' where we take a graph and'lift' it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one). |
| first_indexed | 2024-09-23T17:08:33Z |
| format | Article |
| id | mit-1721.1/137303 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:08:33Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1373032023-01-18T15:57:41Z High-precision Estimation of Random Walks in Small Space Ahmadinejad, AmirMahdi Kelner, Jonathan Murtagh, Jack Peebles, John Sidford, Aaron Vadhan, Salil Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2020 IEEE. In this paper, we provide a deterministic tilde{O}(log N)-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error (epsilon=1 text{poly}(N)) where N is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space O(log N) (following Aleliunas et al., FOCS'79) and by a deterministic algorithm using space O(log{3/2}N) (Saks and Zhou, FOCS'95 and JCSS'99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible (epsilon=1/N{omega(1)}), generalizing what Hoza and Zuckerman (FOCS'18) recently showed for the special case of distinguishing whether a random walk probability is 0 or greater than epsilon. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic tilde{O}(log N)-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS'17) that gave a deterministic tilde{O}(log N)-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS'19) that gave a randomized tilde{O}(N)-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of'cycle-lifted graphs,' where we take a graph and'lift' it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one). 2021-11-03T18:38:47Z 2021-11-03T18:38:47Z 2020-11 2021-05-24T12:56:49Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137303 Ahmadinejad, AmirMahdi, Kelner, Jonathan, Murtagh, Jack, Peebles, John, Sidford, Aaron et al. 2020. "High-precision Estimation of Random Walks in Small Space." Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2020-November. en 10.1109/focs46700.2020.00123 Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Ahmadinejad, AmirMahdi Kelner, Jonathan Murtagh, Jack Peebles, John Sidford, Aaron Vadhan, Salil High-precision Estimation of Random Walks in Small Space |
| title | High-precision Estimation of Random Walks in Small Space |
| title_full | High-precision Estimation of Random Walks in Small Space |
| title_fullStr | High-precision Estimation of Random Walks in Small Space |
| title_full_unstemmed | High-precision Estimation of Random Walks in Small Space |
| title_short | High-precision Estimation of Random Walks in Small Space |
| title_sort | high precision estimation of random walks in small space |
| url | https://hdl.handle.net/1721.1/137303 |
| work_keys_str_mv | AT ahmadinejadamirmahdi highprecisionestimationofrandomwalksinsmallspace AT kelnerjonathan highprecisionestimationofrandomwalksinsmallspace AT murtaghjack highprecisionestimationofrandomwalksinsmallspace AT peeblesjohn highprecisionestimationofrandomwalksinsmallspace AT sidfordaaron highprecisionestimationofrandomwalksinsmallspace AT vadhansalil highprecisionestimationofrandomwalksinsmallspace |