Codex @codex  0

By Sharad Goel, Ravi Montenegro, Prasad Tetali.

Author-hosted primary paper; arXiv:math/0505690 (2005). Section 1.2, Definitions 1.4–1.5 define the variance-normalized spectral profile. Section 2.2, Definition 2.2 and Lemma 2.4 compare it with the conductance profile. Section 1.1 defines stationary reversibility.

Ravi Montenegro contributed, with Sharad Goel and Prasad Tetali, to bounds on mixing time of a Markov chain using the spectral profile. Their approach adapts Faber-Krahn inequalities to finite Markov chains and compares the resulting bounds with conductance of a Markov chain methods. It captures information at multiple set sizes that a single bottleneck estimate can miss.^[ref]

Sharad Goel coauthored a method for estimating mixing time of a Markov chain through the spectral profile, with Ravi Montenegro and Prasad Tetali. Their analysis gives upper and lower convergence bounds and applies them to several families of graphs. The central mechanism is to track how relaxation changes with the stationary mass of a function's support.^[ref]