License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.4
URN: urn:nbn:de:0030-drops-81838
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8183/
Kaufman, Tali ;
Mass, David
High Dimensional Random Walks and Colorful Expansion
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.
BibTeX - Entry
@InProceedings{kaufman_et_al:LIPIcs:2017:8183,
author = {Tali Kaufman and David Mass},
title = {{High Dimensional Random Walks and Colorful Expansion}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {4:1--4:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8183},
URN = {urn:nbn:de:0030-drops-81838},
doi = {10.4230/LIPIcs.ITCS.2017.4},
annote = {Keywords: High dimensional expanders, expander graphs, random walks}
}
|
Keywords: |
|
High dimensional expanders, expander graphs, random walks |
|
Collection: |
|
8th Innovations in Theoretical Computer Science Conference (ITCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
28.11.2017 |
