High Dimensional Random Walks and Colorful Expansion

Authors Tali Kaufman, David Mass



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.4.pdf
  • Filesize: 0.55 MB
  • 27 pages

Document Identifiers

Author Details

Tali Kaufman
David Mass

Cite AsGet BibTex

Tali Kaufman and David Mass. High Dimensional Random Walks and Colorful Expansion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 4:1-4:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.4

Abstract

Random walks on bounded degree expander graphs have numerous applications, both in theoretical and practical computational problems. A key property of these walks is that they converge rapidly to their stationary distribution. In this work we define high order random walks: These are generalizations of random walks on graphs to high dimensional simplicial complexes, which are the high dimensional analogues of graphs. A simplicial complex of dimension d has vertices, edges, triangles, pyramids, up to d-dimensional cells. For any 0 \leq i < d, a high order random walk on dimension i moves between neighboring i-faces (e.g., edges) of the complex, where two i-faces are considered neighbors if they share a common (i+1)-face (e.g., a triangle). The case of i=0 recovers the well studied random walk on graphs. We provide a local-to-global criterion on a complex which implies rapid convergence of all high order random walks on it. Specifically, we prove that if the 1-dimensional skeletons of all the links of a complex are spectral expanders, then for all 0 \le i < d the high order random walk on dimension i converges rapidly to its stationary distribution. We derive our result through a new notion of high dimensional combinatorial expansion of complexes which we term colorful expansion. This notion is a natural generalization of combinatorial expansion of graphs and is strongly related to the convergence rate of the high order random walks. We further show an explicit family of bounded degree complexes which satisfy this criterion. Specifically, we show that Ramanujan complexes meet this criterion, and thus form an explicit family of bounded degree high dimensional simplicial complexes in which all of the high order random walks converge rapidly to their stationary distribution.
Keywords
  • High dimensional expanders
  • expander graphs
  • random walks

Metrics

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

References

  1. N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. Google Scholar
  2. I. Dinur. The pcp theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007. Google Scholar
  3. S. Evra, K. Golubev, and A. Lubotzky. Mixing Properties and the Chromatic Number of Ramanujan Complexes. International Mathematics Research Notices, 2015(22):11520-11548, 2015. Google Scholar
  4. S. Evra and T. Kaufman. Bounded degree cosystolic expanders of every dimension. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 36-48, 2016. Google Scholar
  5. H. Garland. p-Adic Curvature and the Cohomology of Discrete Subgroups of p-Adic Groups. Annals of Mathematics, 97(3):375-423, 1973. Google Scholar
  6. M. Gromov. Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry. Geometric And Functional Analysis, 20(2):416-526, 2010. Google Scholar
  7. A. Gundert and U. Wagner. On Laplacians of Random Complexes. In Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, pages 151-160. ACM, 2012. Google Scholar
  8. S. Hoory, N. Linial, and A. Wigderson. Expander Graphs and their Applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  9. T. Kaufman, D. Kazhdan, and A. Lubotzky. Ramanujan Complexes and Bounded Degree Topological Expanders. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 484-493, 2014. Google Scholar
  10. T. Kaufman and A. Lubotzky. High dimensional expanders and property testing. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 501-506, 2014. Google Scholar
  11. L. Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2:1-46, 1993. Google Scholar
  12. A. Lubotzky. Expander graphs in pure and applied mathematics. Bulletin of the American Mathematical Society, 49(1):113-162, 2012. Google Scholar
  13. A. Lubotzky. Ramanujan complexes and high dimensional expanders. Japanese Journal of Mathematics, 9(2):137-169, 2014. Google Scholar
  14. A. Lubotzky, B. Samuels, and U. Vishne. Explicit constructions of ramanujan complexes of type Ã_d. European Journal of Combinatorics, 26(6):965-993, 2005. Google Scholar
  15. A. Lubotzky, B. Samuels, and U. Vishne. Ramanujan complexes of type Ã_d. Israel Journal of Mathematics, 149(1):267-299, 2005. Google Scholar
  16. I. Oppenheim. Isoperimetric Inequalities and topological overlapping for quotients of Affine buildings. arXiv:1501.04940, 2015. Google Scholar
  17. O. Parzanchevski and R. Rosenthal. Simplicial complexes: spectrum, homology and random walks. arXiv:1211.6775, 2012. Google Scholar
  18. A. Sinclair and M. Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, 1989. Google Scholar
  19. M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. Google Scholar
  20. D. A. Spielman. Computationally efficient error-correcting codes and holographic proofs. PhD thesis, Massachusetts Institute of Technology, 1995. Google Scholar
  21. L. Trevisan. Cheeger-type Inequalities for λ_n. http://lucatrevisan.wordpress.com/2016/02/09/cheeger-type-inequalities-for-%CE%BBn/, 2016.
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