Document Open Access Logo

Deterministic Approximation of Random Walks in Small Space

Authors Jack Murtagh, Omer Reingold, Aaron Sidford, Salil Vadhan

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2019.42.pdf
  • Filesize: 0.57 MB
  • 22 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Random walks and Markov chains
Keywords
  • random walks
  • space complexity
  • derandomization
  • spectral approximation
  • expander graphs

Metrics

Abstract

We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph G, a positive integer r, and a set S of vertices, approximates the conductance of S in the r-step random walk on G to within a factor of 1+epsilon, where epsilon>0 is an arbitrarily small constant. More generally, our algorithm computes an epsilon-spectral approximation to the normalized Laplacian of the r-step walk.
Our algorithm combines the derandomized square graph operation [Eyal Rozenman and Salil Vadhan, 2005], which we recently used for solving Laplacian systems in nearly logarithmic space [Murtagh et al., 2017], with ideas from [Cheng et al., 2015], which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even r (while ours works for all r). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd r. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.

Cite As Get BibTex

Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. Deterministic Approximation of Random Walks in Small Space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 42:1-42:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.42

Author Details

Jack Murtagh
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA
Omer Reingold
  • Computer Science Department, Stanford University, Stanford, CA USA
Aaron Sidford
  • Management Science & Engineering, Stanford University, Stanford, CA USA
Salil Vadhan
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA

Funding

  • Murtagh, Jack: Supported by NSF grant CCF-1763299.
  • Reingold, Omer: Supported by NSF grant CCF-1763311.
  • Vadhan, Salil: Supported by NSF grant CCF-1763299.

References

  1. Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979), pages 218-223. IEEE, New York, 1979. Google Scholar
  2. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289-304, 1992. See also addendum in issue 4(1), 1993, pp. 199-120. URL: https://doi.org/10.1002/rsa.3240030308.
  3. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom Generators for Regular Branching Programs. In FOCS, pages 40-47. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.11.
  4. Joshua Brody and Elad Verbin. The Coin Problem and Pseudorandomness for Branching Programs. In FOCS, pages 30-39. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.10.
  5. Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. Spectral sparsification of random-walk matrix polynomials. arXiv preprint, 2015. URL: http://arxiv.org/abs/1502.03496.
  6. Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu. Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.00755.
  7. Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 583-592. IEEE, 2016. Google Scholar
  8. Anindya De. Pseudorandomness for Permutation and Regular Branching Programs. In IEEE Conference on Computational Complexity, pages 221-231. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/CCC.2011.23.
  9. Ofer Gabber and Zvi Galil. Explicit Constructions of Linear-Sized Superconcentrators. J. Comput. Syst. Sci., 22(3):407-420, 1981. URL: https://doi.org/10.1016/0022-0000(81)90040-4.
  10. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for Network Algorithms. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 356-364, Montréal, Québec, Canada, 1994. Google Scholar
  11. Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani. Density Independent Algorithms for Sparsifying k-Step Random Walks. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh S. Vempala, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), volume 81 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:17, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.14.
  12. Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva. A Framework for Analyzing Resparsification Algorithms. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), volume abs/1611.06940. ACM, 2016. URL: http://arxiv.org/abs/1611.06940.
  13. Yin Tat Lee, Richard Peng, and Daniel A. Spielman. Sparsified Cholesky Solvers for SDD linear systems. CoRR, abs/1506.08204, 2015. URL: http://arxiv.org/abs/1506.08204.
  14. G. A. Margulis. Explicit constructions of expanders. Problemy Peredači Informacii, 9(4):71-80, 1973. Google Scholar
  15. Milena Mihail. Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders. In 30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, North Carolina), pages 526-531. IEEE, 1989. Google Scholar
  16. Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 801-812, 2017. URL: https://doi.org/10.1109/FOCS.2017.79.
  17. Joseph Naor and Moni Naor. Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM J. Comput., 22(4):838-856, 1993. Google Scholar
  18. Richard Peng and Daniel A. Spielman. An Efficient Parallel Solver for SDD Linear Systems. STOC, 2014. Google Scholar
  19. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):Art. 17, 24, 2008. Google Scholar
  20. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Annals of Mathematics, 155(1), January 2001. Google Scholar
  21. Eyal Rozenman and Salil Vadhan. Derandomized Squaring of Graphs. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM `05), number 3624 in Lecture Notes in Computer Science, pages 436-447, Berkeley, CA, August 2005. Springer. Google Scholar
  22. Michael Saks and Shiyu Zhou. BP_H SPACE(S) ⊆ DSPACE(S^(3/2)). Journal of Computer and System Sciences, 58(2):376-403, 1999. Google Scholar
  23. Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81-90. ACM, 2004. Google Scholar
  24. Thomas Steinke. Pseudorandomness for Permutation Branching Programs Without the Group Theory. Technical Report TR12-083, Electronic Colloquium on Computational Complexity (ECCC), July 2012. URL: http://eccc.hpi-web.de/report/2012/083/.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact