A semidefinite bound for mixing rates of Markov chains

We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log²n, where n is the number of states. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 299–313 (1997)