Counting and sampling problems arise in areas such as statistics (benchmarking statistical tests, or sampling from a posterior distribution) and statistical physics (computing the partition function of spin system). Computationally, these problems are very different in character from decision or optimization problems, and their solution requires distinctive techniques. We treat counting and sampling together in this Dagstuhl Seminar, as they are closely related computationally: subject to a reasonable side condition, an efficient algorithm for sampling certain combinatorial structures can be used as a black box to approximately count those structures, and vice versa. Although much attention has been directed towards the complexity of counting and sampling problems, our understanding of them is not as well developed as it is of decision and optimization problems. This Dagstuhl Seminar marks a timely return to the topic, as new ideas have recently been injected into the area, resulting in renewed activity and progress. It is particularly satisfying to observe that much of this progress has been in the positive direction, in the form of new efficient algorithms. This is in an area where negative results had become the norm.

In this Dagstuhl Seminar we will engage with the following topics, though the list is not exclusive.

• MCMC renaissance. Historically, Markov chain Monte Carlo (MCMC) has been the most important approach to designing efficient algorithms for counting and sampling problems. After a lull, MCMC has started advancing again. The main challenge is to derive good bounds on “mixing time”, i.e., the time that elapses until a Markov chain is close to equilibrium. A dramatic example of recent progress is provided by the work on "high-dimensional expanders" which has solved a long-standing conjecture in this area and, in so doing, provided efficient samplers for some natural structures, where none were previously known.
• Deterministic approximate counting. The possibility of efficient deterministic solutions to approximate counting problems became apparent with the arrival of algorithms based on “decay of correlations”. A different approach, based on Taylor expansion in a zero-free region of the partition function, was developed more recently. Originally yielding subexponential algorithms, the approach has seen further advances, pushing the running time down to truly polynomial. Rapid progress is currently being made, powered in part by ideas from statistical physics, for example cluster expansions.
• Counting and sampling for computationally hard problems. Many counting and approximate sampling problems are NP-hard. Parameterised and fine-grained complexity analysis both aim to mitigate the impact of exponential growth rates in running time. In one case the idea is make the algorithm responsive to some beneficial property of problem instances, and in the other to reduce as far as possible the rate of exponential growth. Strong progress is being made, drawing on tools from diverse topics in algebra, probability and combinatorics.
• Computational complexity of restricted instances. Another approach to coping with computational intractability is to focus attention on some restricted class of problem instances. In the field of graph algorithms, restricted graph classes have always been of interest. Now, researchers are investigating a wider selection of graph classes, going beyond the obvious ones such a planar or bipartite. The aim is to draw a more refined boundary between tractable and intractable instances. In this context, hereditary graph classes (ones closed under taking induced subgraphs) are central, as they allow for recursive treatment of problems.
• Exact sampling. Exact sampling of combinatorial structures goes back to Coupling From The Past (CFTP) and beyond that to rejection sampling. Various exact sampling algorithms in the literature radically speed up rejection sampling by resampling only a small number of carefully selected variables at each iteration. Using ideas taken from algorithmic versions of the Lovász Local Lemma, it is possible to give a general account of these algorithms. This viewpoint aids the construction of new algorithms. Making further progress on the above topics requires expertise from a range of disciplines. For this Dagstuhl Seminar, we bring together researchers from a variety of backgrounds to share their recent work, examine promising new approaches and plot a way forward.

Creative Commons BY 3.0 DE

Holger Dell, Mark R. Jerrum, and Haiko Müller