13. – 18. Januar 2013, Dagstuhl Seminar 13031
1 / 2 >
Auskunft zu diesem Dagstuhl Seminar erteilt
Creative Commons BY 3.0 Unported license
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, and Pascal Koiran
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 R. Jerrum, and Pascal Koiran
Dagstuhl Seminar Series
- Data Structures / Algorithms / Complexity
- Exact counting
- Approximate counting
- Holographic algorithms
- Computational complexity of counting
- Algebraic complexity of counting
- Applications to constraint satisfaction
- Graph polynomials