The computational complexity of approximation of partition functions

McQuillan, Colin The computational complexity of approximation of partition functions. Doctor of Philosophy thesis, University of Liverpool.

PDF McQuillanCol_Sep2013_12893.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution No Derivatives. Download (2MB)

Abstract

This thesis studies the computational complexity of approximately evaluating partition functions. For various classes of partition functions, we investigate whether there is an FPRAS: a fully polynomial randomised approximation scheme. In many of these settings we also study “expressibility”, a simple notion of defining a constraint by combining other constraints, and we show that the results cannot be extended by expressibility reductions alone. The main contributions are: -� We show that there is no FPRAS for evaluating the partition function of the hard-core gas model on planar graphs at fugacity 312, unless RP = NP. -� We generalise an argument of Jerrum and Sinclair to give FPRASes for a large class of degree-two Boolean #CSPs. -� We initiate the classification of degree-two Boolean #CSPs where the constraint language consists of a single arity 3 relation. -� We show that the complexity of approximately counting downsets in directed acyclic graphs is not affected by restricting to graphs of maximum degree three. -� We classify the complexity of degree-two #CSPs with Boolean relations and weights on variables. -� We classify the complexity of the problem #CSP(F) for arbitrary finite domains when enough non-negative-valued arity 1 functions are in the constraint language. -� We show that not all log-supermodular functions can be expressed by binary logsupermodular functions in the context of #CSPs.

Item Type:	Thesis (Doctor of Philosophy)
Additional Information:	Date: 2013-09 (completed)
Subjects:	?? QA75 ??
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	12 Feb 2014 12:07
Last Modified:	16 Dec 2022 04:39
DOI:	10.17638/00012893
Supervisors:	Goldberg, Leslie Anne Martin, Russell ORCID: 0000-0002-7043-503X
URI:	https://livrepository.liverpool.ac.uk/id/eprint/12893