Dagstuhl-Seminar 17341
Computational Counting
( 20. Aug – 25. Aug, 2017 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/17341
Organisatoren
- Ivona Bezáková (Rochester Institute of Technology, US)
- Leslie Ann Goldberg (University of Oxford, GB)
- Mark R. Jerrum (Queen Mary University of London, GB)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
Impacts
- Algorithmic Pirogov-Sinai theory - Helmuth, Tyler; Perkins, Will; Regts, Guus - Cornell University : arXiv.org, 2018. - 40 pp..
- Counting Hypergraph Colourings in the Local Lemma Regime : article in STOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - Guo, Heng; Liao, Chao; Lu, Pinyan; Zhang, Chihao - New York : ACM, 2018. - Pages 926-939.
- Extensor-Coding : article in STOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - Brand, Cornelius; Dell, Holger; Husfeldt, Thore - New York : ACM, 2018. - Pages 151-164.
- Note on “The Complexity of Counting Surjective Homomorphisms and Compactions" : article - Dell, Holger - Cornell University : arXiv.org, 2018. - 3 pp..
- Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling : article in ICALP 2018 - Guo, Heng; Jerrum, Mark R. - Wadern : LZI, 2018. - 10 pp. - (Leibniz International Proceedings in Informatics : 107 : article).
Programm
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.
Creative Commons BY 3.0 DE
Ivona Bezakova, Leslie Ann Goldberg, and Mark R. Jerrum
Computational counting problems arise in practical applications in many fields such as statistical physics, information theory and machine learning. 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 computational complexity of counting problems requires a coherent set of techniques which are different in flavour from those employed 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 approximation, randomisation, as well as viewing computational counting through the lens of parameterised complexity, where the goal is to find algorithms that are efficient when some key parameter is "small". Intractability thresholds often relate to "phase transitions" as these key parameters vary. Great progress has been made in recent years towards understanding the complexity of approximate counting, based largely on a connection with these phase transitions.
Specific themes identified for consideration at the meeting included:
- 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.
- Constraint satisfaction problems and the more general Holant framework. The partition functions of many models in statistical physics are included within this setting.
In the event, the talks ranged more widely than this list suggests.
Although the topic of Computational Counting has been explored at various meetings, including at Dagstuhl, for a number of years, it continues to retain its freshness. New approaches are found, new insights are gained, and new connections drawn with other areas both inside and outside computer science. Among the new directions that have emerged since the previous Dagstuhl Seminar in this series are the following.
- Results from quantum information theory applied to the apparently unrelated task of classifying the complexity of Holant problems. (Refer to the talk by Miriam Backens.)
- A new paradigm for designing polynomial-time algorithms for approximating partition functions with complex parameters. This is based on Taylor expansion in a zero-free region of the parameter space combined with an ingenious approach to enumerating small substructures. (Refer to talks by Alexander Barvinok, Jingcheng Liu, Viresh Patel and Guus Regts.)
- Emerging connections between the Lovász Local Lemma - specifically the Shearer condition and the Moser-Tardos algorithmic version - and sampling and approximate counting. (Refer to talks by Andreas Galanis and Heng Guo.)
Ivona Bezáková, Leslie Ann Goldberg, and Mark R. Jerrum
- Miriam Backens (University of Bristol, GB) [dblp]
- Eleni Bakali (National Technical University of Athens, GR) [dblp]
- Alexander Barvinok (University of Michigan - Ann Arbor, US) [dblp]
- Ivona Bezáková (Rochester Institute of Technology, US) [dblp]
- Antonio Blanca (Georgia Institute of Technology - Atlanta, US) [dblp]
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Cornelius Brand (Universität des Saarlandes, DE) [dblp]
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Sarah Cannon (Georgia Institute of Technology - Atlanta, US) [dblp]
- Amin Coja-Oghlan (Goethe-Universität - Frankfurt am Main, DE) [dblp]
- Radu Curticapean (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Holger Dell (Universität des Saarlandes, DE) [dblp]
- Martin Dyer (University of Leeds, GB) [dblp]
- Charis Efthymiou (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Jacob Focke (University of Oxford, GB) [dblp]
- Andreas Galanis (University of Oxford, GB) [dblp]
- David Gamarnik (MIT - Camridge, US) [dblp]
- Andreas Göbel (Hasso-Plattner-Institut - Potsdam, DE) [dblp]
- Leslie Ann Goldberg (University of Oxford, GB) [dblp]
- Catherine Greenhill (UNSW Sydney, AU) [dblp]
- Heng Guo (Queen Mary University of London, GB) [dblp]
- Thomas Hayes (University of New Mexico - Albuquerque, US) [dblp]
- Miki Hermann (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Thore Husfeldt (IT University of Copenhagen, DK) [dblp]
- Mark R. Jerrum (Queen Mary University of London, GB) [dblp]
- John Lapinskas (University of Oxford, GB) [dblp]
- Jingcheng Liu (University of California - Berkeley, US) [dblp]
- Kitty Meeks (University of Glasgow, GB) [dblp]
- Sarah Miracle (University of St. Thomas - St. Paul, US) [dblp]
- Viresh Patel (University of Amsterdam, NL) [dblp]
- Will Perkins (University of Birmingham, GB) [dblp]
- Dana Randall (Georgia Institute of Technology - Atlanta, US) [dblp]
- Guus Regts (University of Amsterdam, NL) [dblp]
- David Richerby (University of Oxford, GB) [dblp]
- Marc Roth (Universität des Saarlandes, DE) [dblp]
- Piyush Srivastava (TIFR Mumbai, IN) [dblp]
- Alexandre Stauffer (University of Bath, GB) [dblp]
- Daniel Stefankovic (University of Rochester, US) [dblp]
- Mingji Xia (Chinese Academy of Sciences - Beijing, CN) [dblp]
- Kuan Yang (University of Oxford, GB) [dblp]
- Yitong Yin (Nanjing University, CN) [dblp]
- Chihao Zhang (The Chinese University of Hong Kong, HK) [dblp]
- Stanislav Živný (University of Oxford, GB) [dblp]
Verwandte Seminare
Klassifikation
- data structures / algorithms / complexity
Schlagworte
- Approximation algorithms
- Computational complexity
- Counting problems
- Partition functions
- Phase transitions
