자료유형 | 학위논문 |
---|---|
서명/저자사항 | Approximate Counting, Phase Transitions and Geometry of Polynomials. |
개인저자 | Liu, Jingcheng. |
단체저자명 | University of California, Berkeley. Electrical Engineering & Computer Sciences. |
발행사항 | [S.l.]: University of California, Berkeley., 2019. |
발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
형태사항 | 117 p. |
기본자료 저록 | Dissertations Abstracts International 81-06B. Dissertation Abstract International |
ISBN | 9781392428795 |
학위논문주기 | Thesis (Ph.D.)--University of California, Berkeley, 2019. |
일반주기 |
Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
Advisor: Sinclair, Alistair. |
이용제한사항 | This item must not be sold to any third party vendors. |
요약 | 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. |
일반주제명 | Computer science. |
언어 | 영어 |
바로가기 |
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |