CMI Seminar: Jingcheng Liu
Approximate counting, phase transitions & geometry of polynomials
In classical statistical physics, a phase transition is understood by studying the geometry (the zero-set) of an associated polynomial (the partition function). In this talk I will show that one can exploit this notion of phase transitions algorithmically, and conversely exploit the analysis of algorithms to understand phase transitions.
As applications, I will give efficient deterministic approximation algorithms (FPTAS) for counting q-colorings, and for computing the partition function of the Ising model.
This talk is fully self-contained, and based on joint work with Alistair Sinclair and Piyush Srivastava.