About
Research on exact and approximate counting problems has seen significant advances recently. The central aim is to understand the computational complexity of these problems and their relationship to phase transitions, especially in statistical physics. Counting problems may be conveniently expressed in terms of the evaluation of partition functions (a sum-of-product computation), and there are three related frameworks for studying them: constraint satisfaction problems, graph homomorphisms, and Holant problems. A satisfactory understanding of a counting problem involves establishing a classification theorem that delineates the regime in which the problem is solvable in polynomial time.
For exact counting, a number of strong dichotomy theorems have been achieved in all three frameworks, though many open problems remain. Furthermore, there is a general thesis that problems can be classified into one of the following three types according to the local constraint functions: (1) P-time computable, (2) #P-hard in general but P-time computable over planar structures, or (3) #P-hard even for planar structures. Moreover, type (2) corresponds to those problems that can be solved by holographic algorithms. The full extent of the validity of this thesis is open.
Classification of problem complexity for approximate counting is more challenging, and new complexity classes arise. For example, the problem #BIS of counting independent sets in a bipartite graph has emerged as a key problem of apparently intermediate complexity. Approximate counting also exhibits strong connections with statistical physics. On the positive side, Markov chain Monte Carlo and correlation decay provide two powerful techniques for achieving polynomial-time approximation algorithms. On the negative side, phase transitions appear to define the boundaries between easy and hard approximation problems.
Phase transitions also arise naturally in the study of random constraint satisfaction problems. Physically motivated algorithmic approaches such as survey propagation perform extremely well for these problems near the phase transition, but a rigorous understanding is only beginning to emerge.
This program brought together researchers from related fields to advance the state of art.
