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

 Electrical Engineering and Computer Sciences (EECS)

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, liuexp@berkeley.edu, 510