Markov chain methods for small-set expansion

Ryan O'Donnell, David Witmer

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…