DocumentCode
1632826
Title
Rapid mixing
Author
Winkler, Peter
Author_Institution
Bell Labs., Lucent Technol., Murray Hill, NJ, USA
fYear
2002
fDate
6/24/1905 12:00:00 AM
Firstpage
102
Lastpage
102
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location
Montreal, Que.
ISSN
1093-0159
Print_ISBN
0-7695-1468-5
Type
conf
DOI
10.1109/CCC.2002.1004347
Filename
1004347
Link To Document