Approximate Counting, Phase Transitions and Geometry of Polynomials
出版項
2019
說明
1 online resource (117 pages)
文字
text
無媒介
computer
成冊
online resource
附註
Source: Dissertations Abstracts International, Volume: 81-06, Section: B
Advisor: Sinclair, Alistair
Thesis (Ph.D.)--University of California, Berkeley, 2019
Includes bibliographical references
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
Electronic reproduction. Ann Arbor, Mich. : ProQuest, 2020
