Author_Institution :
Bell Labs., Lucent Technol., Murray Hill, NJ, USA
fDate :
6/24/1905 12:00:00 AM
Abstract :
Summary form only given. In the past decade many proofs of tractability, have involved showing that some Markov chain "mixes rapidly". We do a fast tour of the highlights of Markov chain mixing, with a view toward answering, or at least addressing, the following questions: What is rapid mixing? How do you prove it, and why would you want to? Does it really have anything to do with computational complexity? And, most disturbing: is there any truth to the rumor that complexity and rapid mixing are related to phase transitions in statistical physics?
Keywords :
Markov processes; computational complexity; Markov chain mixing; computational complexity; rapid mixing; statistical physics; tractability proofs; Computational complexity; Physics;
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-7695-1468-5
DOI :
10.1109/CCC.2002.1004347
