28. November – 03. Dezember 2010, Dagstuhl Seminar 10481
Auskunft zu diesem Dagstuhl Seminar erteilt
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 will cover 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 favour from other algorithmic branches of computer science and is less well-studied than its optimisation counterpart.
Specific topics to be covered by 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 and reductions, computational complexity of counting, algebraic complexity of counting, applications to statistical physics, and applications 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 is 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 = 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.
The seminar brought together 36 researchers from Canada, China, Europe, India, Israel, and the United States with interests and expertise in different aspects of computational counting. Among them there was a good mix of senior parti\-cipants, postdoctoral researchers and PhD students. Altogether, there were 36 talks over the week including three overview presentations and 7 ultra short five minute introductions by those participants that did not wish to give a full talk.
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 participants' feedback. It was an intense week with relatively tight schedule. Still, there were stimulating discussions in the afternoon breaks and in the evenings, some of them even leading to improvements of results that had been presented in the talks. New contacts and maybe even friendships were made.
Dagstuhl Seminar Series
- Data Structures / Algorithms / Complexity
- Exact counting
- Approximate counting
- Holographic algorithms
- Computational complexity of counting
- Algebraic complexity of counting
- Applications to statistical physics
- Applications to constraint satisfaction