Efficient algorithms for low-temperature spin systems

Abstract: Two fundamental algorithmic tasks associated to discrete statistical mechanics models are approximate counting and approximate sampling. At high temperatures Markov chains give efficient algorithms, but at low temperatures mixing times can become impractically large, and Markov chain methods may fail to be efficient. Recently, expansion methods (cluster expansions, Pirogov--Sinai theory) have been put to use to develop provably efficient low-temperature algorithms for some discrete statistical mechanics models. I’ll introduce these algorithmic tasks, outline how expansion algorithms work, and indicate some open directions.

mathematical physics

Audience: researchers in the discipline

( video )

One world IAMP mathematical physics seminar

Series comments: In order to receive announcements, please send an email to IAMPseminars@gmail.com with “subscribe” in the subject line.