Fetching the paper…

Reading the bibliography…

2012

Markov chain methods for small-set expansion

O'Donnell, Ryan, Witmer, David

Original
PDF
Post on X

Understand

Consider a finite irreducible Markov chain with invariant distribution $\pi$.

We use the inner product induced by $\pi$ and the associated heat operator to simplify and generalize some results related to graph partitioning and the small-set expansion problem.
For example, Steurer showed a tight connection between the number of small eigenvalues of a graph's Laplacian and the expansion of small sets in that graph.
We give a simplified proof which generalizes to the nonregular, directed case.

Markov chain methods for small-set expansion · Around

Built on

λ 1 \lambda_{1} , isoperimetric inequalities for graphs, and superconcentrators
Noga Alon and Vitali Milman · 1985
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Approximate counting, uniform generation and rapidly mixing Markov chains
Alistair Sinclair and Mark Jerrum · 1989
Earlier work this paper cites.
Logarithmic Sobolev inequalities for finite Markov chains
Persi Diaconis and Laurent Saloff-Coste · 1996
Earlier work this paper cites.
Faster mixing via average conductance
Lászlo Lovász and Ravi Kannan · 1999
Earlier work this paper cites.

Similar

Mixing time bounds via the spectral profile
Sharad Goel, Ravi Montenegro, and Prasad Tetali · 2006
Cited alongside, same era.
Mathematical aspects of mixing times in Markov chains
Ravid Montenegro and Prasad Tetali · 2006
Cited alongside, same era.
Subexponential algorithms for Unique Games and related problems
Sanjeev Arora, Boaz Barak, and David Steurer · 2010
Cited alongside, same era.
Graph expansion and the Unique Games Conjecture
Prasad Raghavendra and David Steurer · 2010
Cited alongside, same era.
On the Complexity of Unique Games and Graph Expansion
David Steurer · 2010
Cited alongside, same era.

Then

Finding small sparse cuts by random walk
Tsz Chiu Kow and Lap Chi Lau · 2012
Closest in time.
Multi-way spectral partitioning and higher-order Cheeger inequalities
James Lee, Shayan Oveis Gharan, and Luca Trevisan · 2012
Closest in time.
Many sparse cuts via higher eigenvalues
Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala · 2012
Closest in time.
Approximating the expansion profile and almost optimal local graph clustering
Original
Shayan Oveis Gharan and Luca Trevisan · 2012
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…