Dagstuhl Seminar 13031
Computational Counting
( Jan 13 – Jan 18, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13031
Organizers
- Peter Bürgisser (Universität Paderborn, DE)
- Leslie Ann Goldberg (University of Liverpool, GB)
- Mark R. Jerrum (Queen Mary University of London, GB)
- Pascal Koiran (ENS - Lyon, FR)
Contact
- Annette Beyer (for administrative matters)
Schedule
Computational complexity is typically concerned with decision problems, but this is a historical accident, arising from the origins of theoretical computer science within logic. Computing applications, on the other hand, typically involve the computation of numerical quantities. These applications broadly fall into two types - optimization problems, in which the goal is to maximize or (minimize) the value of a function, and counting problems, broadly interpreted, by which me mean computing sums, weighted sums, and integrals including, for example, the expectation of a random variable or the probability of an event. This meeting focuses on all aspects of computational counting, including applications, algorithmic techniques and complexity. Computational counting offers a coherent set of problems and techniques which is different in flavor from other algorithmic branches of computer science and is less well-studied than its optimization counterpart.
Specific topics to be addressed at the meeting include:
- Techniques for exact counting, especially moderately exponential algorithms for intractable problems,
- Techniques for approximate counting including Markov Chain Monte Carlo (MCMC),
- Holographic algorithms,
- Computational complexity of counting,
- Algebraic complexity of counting,
- Applications to constraint satisfaction, and
- Applications to graph polynomials.
Each of these topics is important in its own right. Building on our initial Computational Counting Seminar (Seminar 10481, which was held in November 2010), this meeting brings the topics together to allow cross-fertilization between the areas. In particular, the first three topics listed above focus on relevant algorithmic methods, the next two focus on foundational complexity issues, and the last two focus on specific application domains. We anticipate that synergy between these different aspects and communities will lead to better understanding and significant progress. The focus on graph polynomials is new in this meeting - this is an outcome of Seminar 10481, where graph polynomials emerged as an important focus across all topics.
Computational complexity is typically concerned with decision problems, but this is a historical accident, arising from the origins of theoretical computer science within logic. Computing applications, on the other hand, typically involve the computation of numerical quantities. These applications broadly fall into two types: optimisation problems and counting problems. We are interested in the latter, broadly interpreted: computing sums, weighted sums, and integrals including, for example, the expectation of a random variable or the probability of an event. The seminar covered all aspects of computational counting, including applications, algorithmic techniques and complexity. Computational counting offers a coherent set of problems and techniques which is different in flavour from other algorithmic branches of computer science and is less well-studied than its optimisation counterpart.
Specific topics covered by the meeting include
- Techniques for exact counting, including moderately exponential algorithms for intractable problems, fixed parameter tractability, and holographic algorithms and reductions;
- techniques for approximate counting including Markov Chain Monte Carlo (MCMC);
- computational complexity of counting, including complexity in algebraic models; and
- applications, for example to models in statistical physics, and to constraint satisfaction.
The questions addressed include: What algorithmic techniques are effective for exact counting and approximate counting? Do these techniques remain effective in the presence of weights (including negative and complex weights)? What inherent limitations arise from computational complexity? Are there inherent limitations for specific techniques such as MCMC? Our nominated application areas prompted many of those questions and hopefully will benefit from the answers.
Although each of these topics is important in its own right, the real goal of this seminar was to bring them together to allow cross-fertilisation. Here is an example. A key issue for MCMC is the rate at which a Markov chain converges to equilibrium, which determines the length of simulation needed to get a good estimate. An important insight has been that this mixing rate is connected to the phenomenon of phase transitions in statistical physics. But it also seems likely that phase transitions are connected with computational intractability more generally, i.e., resistance to all efficient approximation algorithms, not just those based on MCMC. A further example is provided by the way algebra pervades several of our topics - holographic algorithms, complexity of counting, and constraint satisfaction - and yet the connections between these are only now being explored. For example, algebraic methods permit semi-automatic generation of reductions between counting problems, and open up the speculative possibility of resolving the P versus NP question positively through "accidental algorithms".
We are interested in the complexity of counting in different models of computation. Counting in models of arithmetic circuits is intimately connected with the permanent versus determinant problem. The latter has recently triggered the study of several specific counting problems such as the computation of Littlewood-Richardson coefficients. Another direction of research that is relevant to the meeting is the classification of counting problems in computational algebraic geometry (counting irreducible factors, connected components, etc).
Two key applications areas, statistical physics and constraint satisfaction, have a central role. The problem of computing and approximating weighted sums already arises frequently in statistical physics, where such sums are referred to as partition functions. Constraint Satisfaction is a wide class of problems which arose in the context of AI - many computer science problems can be cast in this framework. Weights are not traditionally considered in CSP, but with this addition, many applications can be viewed in terms of counting CSPs.
Participation and Programme
The seminar brought together 43 researchers from Canada, China, Europe, India, Israel, Japan and the United States with interests and expertise in different aspects of computational counting. Among them there was a good mix of senior participants, postdoctoral researchers and PhD students. Altogether, there were 32 talks over the week.
If the spread of talks at the meeting is a reliable guide, the most active topics in the field at the moment are: algorithms and complexity in algebraic models, the complexity of Counting CSPs (Constraint Satisfaction Problems), and holographic algorithms and the holant framework. Other topics covered included: graph polynomials, MCMC (Markov Chain Monte Carlo) algorithms, parameterised complexity, phase transitions/decay of correlation and its relation to computational complexity, streaming algorithms, and exponential-time exact algorithms. In addition to the technical presentations listed in the online programme, there were tutorial-style talks on topics featured in the Seminar. On Monday afternoon, Tyson Williams introduced the audience to holant problems and holographic transformations, and on Tuesday, Thore Husfeldt provided a similar service for newcomers to ETH and #ETH (the "Exponential Time Hypothesis" and its counting analogue).
One of the main aims of the seminar was to bring together researchers from different, but related fields, covering all aspects of computational counting with the goal of fostering the exchange of knowledge and to stimulate new research. This goal was fully achieved according to our opinion and the participant's feedback. The programme was as usual a compromise between allowing sufficient time for participants to present their work, while also providing unstructured periods for informal discussions. New contacts and maybe even friendships were made.
Snow and an early sunset did not the prevent the traditional Wednesday "hike" from taking place, though they did curtail it somewhat. The scenery was enhanced by the recent snowfall.
The organisers and participants thank the staff and the management of Schloss Dagstuhl for their assistance and support in the arrangement of a very successful and productive meeting.
Creative Commons BY 3.0 Unported license
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Magnus Bordewich (Durham University, GB) [dblp]
- Irénée Briquel (Université d'Orléans, FR) [dblp]
- Andrei A. Bulatov (Simon Fraser University - Burnaby, CA) [dblp]
- Peter Bürgisser (Universität Paderborn, DE) [dblp]
- Xi Chen (Columbia University - New York, US) [dblp]
- Radu Curticapean (Universität des Saarlandes, DE) [dblp]
- Holger Dell (University of Wisconsin - Madison, US) [dblp]
- Arnaud Durand (University Paris-Diderot, FR) [dblp]
- Martin Dyer (University of Leeds, GB) [dblp]
- Jo Ellis-Monaghan (Saint Michael's College - Colchester, US) [dblp]
- Hervé Fournier (University Paris-Diderot, FR) [dblp]
- Andreas Göbel (University of Liverpool, GB) [dblp]
- Leslie Ann Goldberg (University of Liverpool, GB) [dblp]
- Bruno Grenet (ENS - Lyon, FR) [dblp]
- Heng Guo (University of Wisconsin - Madison, 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]
- Marek Karpinski (Universität Bonn, DE) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
- Johann A. Makowsky (Technion - Haifa, IL) [dblp]
- Guillaume Malod (University Paris-Diderot, FR) [dblp]
- Colin McQuillan (University of Liverpool, GB) [dblp]
- Kitty Meeks (Queen Mary University of London, GB) [dblp]
- Stefan Mengel (Universität Paderborn, DE) [dblp]
- Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
- Natacha Portier (ENS - Lyon, FR) [dblp]
- David Richerby (University of Liverpool, GB) [dblp]
- Peter Scheiblechner (Hochschule Luzern, CH) [dblp]
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Daniel Stefankovic (University of Rochester, US) [dblp]
- Yann Strozecki (University of Versailles, FR) [dblp]
- He Sun (MPI für Informatik - Saarbrücken, DE) [dblp]
- Sébastien Tavenas (ENS - Lyon, FR) [dblp]
- Leslie Valiant (Harvard University - Cambridge, US) [dblp]
- Pascal Vontobel (HP Labs - Palo Alto, US) [dblp]
- William Whistler (Durham University, GB)
- Tyson Williams (University of Wisconsin - Madison, US) [dblp]
- Mingji Xia (MPI für Informatik - Saarbrücken, DE) [dblp]
- Tomoyuki Yamakami (University of Fukui, JP) [dblp]
- Chihao Zhang (Shanghai Jiao Tong University, CN) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
Keywords
- exact counting
- approximate counting
- holographic algorithms
- computational complexity of counting
- algebraic complexity of counting
- applications to constraint satisfaction
- graph polynomials
