https://www.dagstuhl.de/22482

27. November – 02. Dezember 2022, Dagstuhl-Seminar 22482

Counting and Sampling: Algorithms and Complexity

Organisatoren

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)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Marsha Kleinbauer zu wissenschaftlichen Fragen

Dagstuhl Reports

Wir bitten die Teilnehmer uns bei der notwendigen Dokumentation zu unterstützen und Abstracts zu ihrem Vortrag, Ergebnisse aus Arbeitsgruppen, etc. zur Veröffentlichung in unserer Serie Dagstuhl Reports einzureichen über unser
Dagstuhl Reports Submission System.

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl-Seminar Wiki
Programm des Dagstuhl-Seminars [pdf] (Aktualisieren)

(Zum Einloggen bitte persönliche DOOR-Zugangsdaten verwenden)

Questionnaire

How do you like this seminar? Please take a survey and receive results by email.
(This link is only visible from within Dagstuhl)

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 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.

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

Dagstuhl-Seminar Series

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

Buchausstellung

Bücher der Teilnehmer

Buchausstellung im Erdgeschoss der Bibliothek

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.