First-order phase transitions and efficient sampling algorithms

9 June 2020
Will Perkins

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.


What is the connection between phase transitions in statistical physics and the computational tractability of approximate counting and sampling? There are many fascinating answers to this question but many mysteries remain. I will discuss one particular type of a phase transition: the first-order phase in the Potts model on $\mathbb{Z}^d$ for large $q$, and show how tools used to analyze the phase transition can be turned into efficient algorithms at the critical temperature. In the other direction, I'll discuss how the algorithmic perspective can help us understand phase transitions.

  • Combinatorial Theory Seminar