Dagstuhl Seminar 22482
Counting and Sampling: Algorithms and Complexity
( Nov 27 – Dec 02, 2022 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/22482
Organizers
- Holger Dell (Goethe-Universität - Frankfurt am Main, DE)
- Mark R. Jerrum (Queen Mary University of London, GB)
- Haiko Müller (University of Leeds, GB)
Contact
- Marsha Kleinbauer (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- The Weisfeiler-Leman Dimension of Existential Conjunctive Queries - Göbel, Andreas; Goldberg, Leslie Ann; Roth, Marc - Cornell University : arXiv.org, 2023. - 36 pp..
- The Weisfeiler-Leman Dimension of Existential Conjunctive Queries - Göbel, Andreas; Goldberg, Leslie Ann; Roth, Marc - Cornell University : arXiv.org, 2023. - 36 pp..
Schedule
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 a spin system). Computationally, these problems are very different in character from decision or optimisation problems, and their solution requires distinctive techniques. It is natural to treat counting and sampling together in the same 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 optimisation problems. This 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.
The Covid pandemic inevitably left its mark on the meeting. Over five years elapsed between the previous Dagstuhl Seminar on a related topic and the current one. In the meantime, the introduction of a circle of ideas around high-dimensional expanders, spectral expansion and entropy decay has transformed the analysis of Markov chains for sampling, and brought many previously intractable questions within scope of our methods. An unwelcome impact of Covid was to reduce significantly the number of participants. Sadly, it was not possible to invite all the people we would have liked to see at the meeting.
With a view to providing a snapshot of current interests, here is a rough-and-ready breakdown of the presentations against a somewhat arbitrary set of headings.
- Connections with statistical physics, phase transitions, etc. Coja-Oghlan, Galanis and Patel,
- Holant and constraint satisfaction problems. Backens and Bulatov.
- Markov chains. Guo and Miracle.
- Parameterised complexity of counting problems. Bressan, Focke, Roth and Wellnitz.
- Perfect samplers. Anand and Cannon.
- Point processes and other geometric connections. Anari, Jerrum and Pappik.
- Polynomials associated with graphs, matroids and matrices. Björklund, Curticapean, Regts.
- Other. Göbel, Goldberg, Kaski, Lapinskas.
If nothing else, this rough classification exercise gives an impression of the wide span of current research. Aside from the progress on the analysis of Markov chains mentioned earlier, many other topics have seen advances in the past five years. Examples include: counting small patterns ("motifs") in large graphs (networks), sampling structures in regions of phase non-uniqueness, perfect sampling, and weighted counting problems where the weights are complex. It turns out that the latter study shines light on the case of real weights, through an examination of zeros of partition functions in the complex plane. The meeting gave participants a long-awaited chance to review developments over the past five years.
On the organisational front, an innovation (as far as this community is concerned) was the inclusion of a problem session on the first day. This went off quite smoothly, and small working groups formed fairly spontaneously to work on problems during the week. On the final day we heard from the groups a summary of their investigations over the week. Our hope is that sufficient momentum was achieved on some of these problems that groups will continue to work on them beyond the end of the meeting. Indeed, one of the working groups decided to apply to run a workshop on homomorphism counting at ICALP 2023 with this aim in mind. The proposal, by Radu Curticapean and Marc Roth, was accepted, and the workshop, entitled "ADjoint HOmomorphism Counting" (AD HOC) will take place in July 2023. We look forward to being able to report on advances achieved on this and other topics on this website.
Creative Commons BY 4.0
Holger Dell, Mark R. Jerrum, and Haiko Müller
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 a spin system). Computationally, these problems are very different in character from decision or optimisation problems, and their solution requires distinctive techniques. It is convenient to group counting and sampling together, as they are closely related computationally: in many situations, an efficient algorithm for sampling certain combinatorial structures can be used as a black box to approximately count those structures, and vice versa.
We expect the following topics will feature prominently at the Dagstuhl Seminar, though this list is not exhaustive:
- Markov Chain Monte Carlo (MCMC) renaissance. MCMC is an approach to sampling structures from complex probability distributions that is based on Markov Chain simulation. The area has seen a sudden burst of activity and progress. For example, the concept of “spectral independence” has enabled optimal (nearly linear time) sampling algorithms to be analysed, even in situations where no polynomial-time sampling algorithm was previously known.
- Deterministic approximate counting. Historically, algorithms for approximate counting have overwhelmingly relied on randomisation. Now, deterministic approaches are available. These are related to the correspondence (from statistical physics) between phase transitions of a system and zeros of the partition function of the system in the complex plane.
- 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 to 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. Although hereditary graph classes have always been of interest, researchers are now investigating a wider selection of classes, going beyond the standard ones such a planar or bipartite. The aim is to draw a more refined boundary between tractable and intractable problem instances.
- Exact sampling. Often, we settle for samples from a distribution that is close to the desired one. Sometimes, however, it is possible to sample perfectly from the desired distribution. Aside from providing a clean solution to a sampling problem, perfect sampling algorithms can often be both simple and more efficient. The range of approaches to perfect sampling has been expanding rapidly.
Great strides have been made in this area in the last few years, with new concepts and tools being introduced. There are deep connections between the various approaches, which still need to be fully explored. At the same time, the recent positive results throw a stronger light on the open problems we need to tackle next.
Making further progress requires expertise from a range of disciplines. For this Dagstuhl Seminar, we aim to bring together researchers from a variety of backgrounds to share their recent work, examine promising new approaches and plot a way forward.
Holger Dell, Mark R. Jerrum, and Haiko Müller
- Konrad Anand (Queen Mary University of London, GB)
- Nima Anari (Stanford University, US)
- Miriam Backens (University of Birmingham, GB) [dblp]
- Andreas Björklund (Lund, SE) [dblp]
- Marco Bressan (University of Milan, IT)
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Sarah Cannon (Claremont McKenna College, US) [dblp]
- Charlie Carlson (University of Colorado - Boulder, US)
- Amin Coja-Oghlan (TU Dortmund, DE) [dblp]
- Radu Curticapean (IT University of Copenhagen, DK) [dblp]
- Ewan Davies (University of Colorado - Boulder, US)
- Holger Dell (Goethe-Universität - Frankfurt am Main, DE) [dblp]
- Martin Dyer (University of Leeds, GB) [dblp]
- Jacob Focke (CISPA - Saarbrücken, DE) [dblp]
- Andreas Galanis (University of Oxford, GB) [dblp]
- Andreas Göbel (Hasso-Plattner-Institut, Universität Potsdam, DE) [dblp]
- Leslie Ann Goldberg (University of Oxford, GB) [dblp]
- Heng Guo (University of Edinburgh, GB) [dblp]
- Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
- Petteri Kaski (Aalto University, FI) [dblp]
- John Lapinskas (University of Bristol, GB) [dblp]
- Sarah Miracle (University of St. Thomas - St. Paul, US) [dblp]
- Haiko Müller (University of Leeds, GB) [dblp]
- Noela Müller (TU Eindhoven, NL)
- Marcus Pappik (Hasso-Plattner-Institut, Universität Potsdam, DE)
- Viresh Patel (Queen Mary University of London, GB) [dblp]
- Guus Regts (University of Amsterdam, NL) [dblp]
- Marc Roth (University of Oxford, GB) [dblp]
- Philip Wellnitz (MPI für Informatik - Saarbrücken, DE) [dblp]
- Stanislav Živný (University of Oxford, GB) [dblp]
Related Seminars
Classification
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- Approximation algorithms
- Computational complexity of counting problems
- Markov chain Monte Carlo
- Statistical physics
- Structural Graph Theory
