http://www.dagstuhl.de/17341

20. – 25. August 2017, Dagstuhl Seminar 17341

Computational Counting

Organisatoren

Ivona Bezakova (Rochester Institute of Technology, US)
Leslie Ann Goldberg (University of Oxford, GB)
Mark R. Jerrum (Queen Mary University of London, GB)

Auskunft zu diesem Dagstuhl Seminar erteilen

Simone Schilke zu administrativen Fragen

Michael Gerke 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]

(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)

Motivation

Computational counting problems arise in practical applications in many fields such as statistical physics, machine learning and computational biology. In such a problem, the goal is to compute or to estimate a weighted sum. Some typical computational counting problems include evaluating a probability, the expectation of a random variable, a partition function or an integral.

The study of the complexity of computational counting problems requires a coherent set of techniques which is different in flavour from techniques found in other algorithmic branches of computer science. Relevant techniques include the analysis of Markov chains, the analysis of correlation decay, parameterised algorithms and complexity, and dichotomy techniques for constructing detailed classifications.

Most computational problems are intractable when considered from the perspective of classical complexity, so it is important to find ways to cope with intractability. These include searching for efficient (possibly randomised) approximation algorithms, or parameterised algorithms that are efficient when some key parameter is "small". Often, the range of applicability of approximation algorithms is limited by the existence of "phase transitions" as some parameter varies. Great progress has been made in recent years towards understanding the complexity of approximate counting, based largely on this connection with phase transitions.

Specific themes of this Dagstuhl Seminar include, but are not limited to, the following.

  • Exact counting, including classifications, quasi-polynomial and/or moderately exponential algorithms for intractable problems, and parameterised algorithms; also complexity-theoretic limitations to obtaining exact solutions.
  • Approximate counting, including Markov Chain Monte Carlo (MCMC) algorithms, and algorithms based on decay of correlations; also complexity-theoretic limitations to obtaining approximate solutions.
  • The interplay between phase transitions and computational tractability.
  • Counting constraint satisfaction problems and holants. The partition functions of many models in statistical physics are included within this setting.

License
  Creative Commons BY 3.0 DE
  Ivona Bezakova and Leslie Ann Goldberg, and Mark R. Jerrum

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Approximation algorithms
  • Computational complexity
  • Counting problems
  • Partition functions
  • Phase transitions

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

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

Publikationen

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

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.