Dissertation Talk: Approximate counting, phase transitions and geometry of polynomials
Seminar: Dissertation Talk: CS | May 3 | 1:30-2:30 p.m. | 306 Soda Hall
Jingcheng Liu, UC Berkeley
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.
CA, firstname.lastname@example.org, 510