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.
Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:592802 |
Date | January 2013 |
Creators | McQuillan, Colin |
Contributors | Goldberg, Leslie Anne; Martin, Russell |
Publisher | University of Liverpool |
Source Sets | Ethos UK |
Detected Language | English |
Type | Electronic Thesis or Dissertation |
Source | http://livrepository.liverpool.ac.uk/12893/ |
Page generated in 0.0016 seconds