Publication: Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
Open/View Files
Date
2017
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Murtagh, Jack, Omer Reingold, Aaron Sidford, Salil Vadhan. 2017. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, October 15-17, 2017.
Research Data
Abstract
We give a deterministic O˜(log n)-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using O(log n) space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using O(log3/2 n) space (Saks and Zhou, FOCS 1995 and JCSS 1999). Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC ‘04; Peng and Spielman, STOC ‘14) with ideas used to show that UNDIRECTED S-T CONNECTIVITY is in deterministic logspace (Reingold, STOC ‘05 and JACM ‘08; Rozenman and Vadhan, RANDOM ‘05).
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service