Fetching the paper…

Reading the bibliography…

High Order Random Walks: Beyond Spectral Gap · Around

2017

High Order Random Walks: Beyond Spectral Gap

Kaufman, Tali, Oppenheim, Izhar

Original
PDF
Post on X

Understand

We study high order random walks in high dimensional expanders; namely, in complexes which are local spectral expanders.

Recent works have studied the spectrum of high order walks and deduced fast mixing.
However, the spectral gap of high order walks is inherently small, due to natural obstructions that do not happen for walks on expander graphs.
In this work we go beyond spectral gap, and relate the shrinkage of a $k$-cochain by the walk operator, to its structure under the assumption of local spectral expansion.

Built on

p p -adic curvature and the cohomology of discrete subgroups of p p -adic groups
Howard Garland · 1973
Earlier work this paper cites.
On L 2 L^{2} -cohomology and property (T) for automorphism groups of polyhedral cell complexes
W. Ballmann and J. Świ ‘ · 1997
Earlier work this paper cites.
On Laplacians of random complexes
Anna Gundert and Uli Wagner · 2012
Earlier work this paper cites.
Making the long code shorter
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer · 2015
Earlier work this paper cites.
Vanishing of cohomology and property (T) for groups acting on weighted simplicial complexes
Izhar Oppenheim · 2015
Earlier work this paper cites.

Similar

Towards a proof of the 2-to-1 games conjecture?
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra · 2016
Cited alongside, same era.
High dimensional expanders imply agreement expanders
Irit Dinur and Tali Kaufman · 2017
Cited alongside, same era.
On non-optimally expanding sets in grassmann graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra · 2017
Cited alongside, same era.
High dimensional combinatorial random walks and colorful expansion
Tali Kaufman and David Mass · 2017
Cited alongside, same era.

Then

Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid
Original
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant · 2018
Closest in time.
Boolean functions on high-dimensional expanders
Original
Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha · 2018
Closest in time.
Local spectral expansion approach to high dimensional expanders Part I: Descent of spectral gaps
Izhar Oppenheim · 2018
Closest in time.
High order random walks: beyond spectral gap
Tali Kaufman and Izhar Oppenheim · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…