This EPSRC-funded research project (EP/E062172/1, EP/E062482/1, EP/E064906/1) runs from Oct 2007 to Sept 2010. The overall aim of the project is to classify the computational complexity of counting in Constraint Satisfaction problems.

• Martin Dyer, School of Computing, University of Leeds,
• Leslie Ann Goldberg, Department of Computer Science, University of Liverpool,
• Mark Jerrum, School of Mathematical Sciences, Queen Mary, University of London.

• Markus Jalsenius, Department of Computer Science, University of Liverpool,
• David Richerby, School of Computing, University of Leeds,

• John Faben, School of Mathematical Sciences, Queen Mary, University of London.

Constraint Satisfaction, which originated in Artificial Intelligence, provides a general framework for modelling decision problems, and has many practical applications. Decisions are modelled by variables, which are subject to constraints, modelling logical and resource restrictions. The paradigm is sufficiently broad that many interesting problems can be modelled, from satisfiability problems to scheduling problems and graph-theory problems. Understanding the complexity of constraint satisfaction problems has become a major and active area within computational complexity. The overall goal is to classify CSPs according to complexity, giving a characterisation for which CSPs are tractable. We will focus especially on characterizing the complexity of counting in Constraint Satisfaction problems. Specifically, we will study the complexity of exactly counting CSP solutions, approximately counting CSP solutions, and sampling CSP solutions from appropriately-defined probability distributions. These important questions are closely related, and are strongly connected to questions in statistical physics.

• L.A. Goldberg and M. Jerrum, Approximating the partition function of the ferromagnetic Potts model, arXiv:1002.0986 [cs.CC] (Feb, 2010) Conference version submitted.
  
  
• M. Dyer, L.A. Goldberg, and M. Jerrum, A complexity dichotomy for hypergraph partition functions, To appear in Computational Complexity
  
  
• J. Faben, The complexity of counting solutions to Generalised Satisfiability Problems modulo k, arXiv:0809.1836v1 [cs.CC] (Sept, 2008)
  
  
• M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby, The Complexity of Approximating Bounded-Degree Boolean #CSP, arXiv:0907.2663v1 [cs.CC] (July, 2009) To Appear in STACS 2010.
  
  
• M. Dyer, L.A. Goldberg, and M. Jerrum, An approximation trichotomy for Boolean #CSP, To Appear in JCSS
  
  
• A. Bulatov, M. Dyer, L.A. Goldberg, M. Jalsenius and D. Richerby, The Complexity of Weighted Booleam #CSP with Mixed Signs, Theoretical Computer Science 410 (2009) 3949--3961 http://dx.doi.org/10.1016/j.tcs.2009.06.003
  
  
• M. Dyer, L.A. Goldberg, and M. Jerrum, The Complexity of Weighted Boolean #CSP, SIAM Journal on Computing 38(5) (Jan 2009) 1970-1986 http://dx.doi.org/10.1137/070690201
  
  
• L.A. Goldberg, M. Grohe, M. Jerrum and M. Thurley, A complexity dichotomy for partition functions with mixed signs, Proceedings of STACS 2009.