Document Open Access Logo

Local Access to Random Walks

Authors Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.24.pdf
  • Filesize: 0.82 MB
  • 22 pages

Document Identifiers

Author Details

Amartya Shankha Biswas
  • CSAIL, MIT, Cambridge, MA, USA
Edward Pyne
  • Harvard University, Cambridge, MA, USA
Ronitt Rubinfeld
  • CSAIL, MIT, Cambridge, MA, USA

Funding

  • Biswas, Amartya Shankha: Big George Ventures Fund, MIT-IBM Watson AI Lab and Research Collaboration Agreement No. W1771646, NSF awards CCF-1733808 and IIS-1741137
  • Rubinfeld, Ronitt: NSF awards CCF-2006664, CCF-1740751, IIS-1741137, Fintech@CSAIL. Part of this work was done while the author was participating in the program on Probability, Geometry, and Computation in High Dimensions at the Simons Institute for the Theory of Computing.

Acknowledgements

We thank the anonymous reviewers for comments that improved our presentation, and for comments that led us to strengthen our results. The second author thanks Andrew Lu for valuable comments on a draft of this paper.

Cite As Get BibTex

Amartya Shankha Biswas, Edward Pyne, and Ronitt Rubinfeld. Local Access to Random Walks. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.24

Abstract

For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting position_G(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/poly(n) close to those of a uniformly random walk in 𝓁₁ distance.
We first give an algorithm for local access to random walks on a given undirected d-regular graph with Õ(1/(1-λ)√n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n,d) are expanders with high probability, this gives an Õ(√n) algorithm for a graph drawn from G(n,d) whp, which improves on the naive method for small numbers of queries.
We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√n/log(n)) per query in expectation when the input graph is drawn from G(n,d), obtaining a nearly matching lower bound. We further show an Ω(n^{1/4}) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance).
We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree n^ε graphs for any ε ∈ (0,1]) and Cartesian product.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • sublinear time algorithms
  • random generation
  • local computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Yuval Roichman. Random Cayley graphs and expanders. Random Struct. Algorithms, 5(2):271-285, 1994. URL: https://doi.org/10.1002/rsa.3240050203.
  2. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1132-1139. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.89.
  3. Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow. On solving linear systems in sublinear time. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 3:1-3:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.3.
  4. Amartya Shankha Biswas, Ronitt Rubinfeld, and Anak Yodpinyanee. Local access to huge random objects through partial sampling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  5. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-316, 1980. Google Scholar
  6. Artur Czumaj, Yishay Mansour, and Shai Vardi. Sublinear graph augmentation for fast query implementation. In Leah Epstein and Thomas Erlebach, editors, Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, volume 11312 of Lecture Notes in Computer Science, pages 181-203. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04693-4_12.
  7. Guy Even, Reut Levi, Moti Medina, and Adi Rosén. Sublinear random access generators for preferential attachment graphs. arXiv preprint arXiv:1602.06159, 2016. Google Scholar
  8. Joel Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. CoRR, cs.DM/0405020, 2004. URL: http://arxiv.org/abs/cs/0405020.
  9. Alan M. Frieze, Navin Goyal, Luis Rademacher, and Santosh S. Vempala. Expanders via random spanning trees. SIAM J. Comput., 43(2):497-513, 2014. URL: https://doi.org/10.1137/120890971.
  10. Anna C Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, Sivaramakrishnan Muthukrishnan, and Martin J Strauss. Fast, small-space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 389-398, 2002. Google Scholar
  11. Oded Goldreich, Shafi Goldwasser, and Asaf Nussboim. On the implementation of huge random objects. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 68-79. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238182.
  12. Oded Goldreich, Shafi Goldwasser, and Asaf Nussboim. On the implementation of huge random objects. SIAM Journal on Computing, 39(7):2761-2822, 2010. Google Scholar
  13. Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electron. Colloquium Comput. Complex., 7(20), 2000. URL: http://eccc.hpi-web.de/eccc-reports/2000/TR00-020/index.html.
  14. Jonathan A. Kelner and Aleksander Madry. Faster generation of random spanning trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 13-21. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.75.
  15. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 364-377. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384303.
  16. Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 2019-2036. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.134.
  17. Brendan D McKay and Nicholas C Wormald. Asymptotic enumeration by degree sequence of graphs with degrees o(n^1/2). Combinatorica, 11(4):369-382, 1991. Google Scholar
  18. Moni Naor and Asaf Nussboim. Implementing huge sparse random graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 596-608. Springer, 2007. Google Scholar
  19. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1-3):183-196, 2007. Google Scholar
  20. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 223-238. Tsinghua University Press, 2011. URL: http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/36.html.
  21. Ronitt Rubinfeld and Arsen Vasilyan. Approximating the noise sensitivity of a monotone boolean function. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 52:1-52:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.52.
  22. Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Distributed random walks. J. ACM, 60(1):2:1-2:31, 2013. URL: https://doi.org/10.1145/2432622.2432624.
  23. Shang-Hua Teng. Independent sets versus perfect matchings. Theor. Comput. Sci., 145(1&2):381-390, 1995. URL: https://doi.org/10.1016/0304-3975(94)00289-U.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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