https://www.dagstuhl.de/21151

April 11 – 16 , 2021, Dagstuhl Seminar 21151

Counting and Sampling: Algorithms and Complexity

Organizers

Holger Dell (IT University of Copenhagen, DK)
Mark R. Jerrum (Queen Mary University of London, GB)
Haiko Müller (University of Leeds, GB)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Michael Gerke for scientific matters

Motivation

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.

Motivation text license
  Creative Commons BY 3.0 DE
  Holger Dell, Mark R. Jerrum, and Haiko Müller

Dagstuhl Seminar Series

Classification

  • Computational Complexity
  • Data Structures And Algorithms
  • Discrete Mathematics

Keywords

  • Complexity of sampling
  • Complexity of counting.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.