Graphical models through the lens of phase transitions

Graphical models are a broad framework from statistics with diverse applications in computer science, such as machine learning and computer vision. Markov chains, message passing algorithms and optimisation techniques are common tools that are used in practice to analyse their statistical properties. Nevertheless, the algorithmic efficiency and accuracy of these methods varies significantly; in fact, even small changes to the parameters of a graphical model can affect heavily their performance, often in a discontinuous way.

We will study these computational transition phenomena by establishing connections to phase transitions in statistical physics. Strikingly, this phase transition perspective often allows us to pinpoint the boundaries of efficient computation, not only for specific algorithms of interest (such as Markov chains or Belief Propagation), but also from a more general computational complexity viewpoint.

Andreas Galanis is a postdoctoral research fellow in the Department of Computer Science at the University of Oxford. During Spring 2016, he was a research fellow at the Simons Institute for the Theory of Computing. He received his Phd in Algorithms, Combinatorics, and Optimization from the School of Computer Science at Georgia Tech. He obtained an MS in mathematics from Georgia Tech, an MS in Logic, Algorithms & Computation from the University of Athens, and a diploma in electrical and computer engineering from the National Technical University of Athens. His research focuses on approximate sampling problems and the analysis of stochastic processes arising in computer science and related areas.