McQuillan, Colin
The computational complexity of approximation of partition functions.
Doctor of Philosophy thesis, University of Liverpool.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/application_pdf.png) |
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: |
|
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/12893 |
Dimensions
Dimensions
