Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Electronic Theses and Dissertations bannerUC Berkeley

Approximate counting, phase transitions and geometry of polynomials

Abstract

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 thesis, we 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, we give efficient deterministic approximation algorithms (FPTAS) for counting $q$-colorings, and for computing the partition function of the Ising model.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View