Approximate counting, phase transitions and geometry of polynomials
Jingcheng Liu
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2019-110
August 1, 2019
This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/Archive/EECS-2019-110.pdf
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.
Advisors: Alistair Sinclair
BibTeX citation:
@phdthesis{Liu:EECS-2019-110,
Author= {Liu, Jingcheng},
Title= {Approximate counting, phase transitions and geometry of polynomials},
School= {EECS Department, University of California, Berkeley},
Year= {2019},
Month= {Aug},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-110.html},
Number= {UCB/EECS-2019-110},
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.},
}
EndNote citation:
%0 Thesis %A Liu, Jingcheng %T Approximate counting, phase transitions and geometry of polynomials %I EECS Department, University of California, Berkeley %D 2019 %8 August 1 %@ UCB/EECS-2019-110 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-110.html %F Liu:EECS-2019-110