12.10.14 - 17.10.14, Seminar 14421

Optimal algorithms and proofs

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Special invitation to Maja Andrack art exhibit opening

Schloss Dagstuhl cordially invites all seminar participants to drop by the New Building at 7:30 p.m. on Monday, October 13 for the opening of the Dagstuhl art exhibition "über * oder über 1." The exhibit features the work of artist Maja Andrack and focuses on the concept of disappearance. Light refreshments will be served.


The notion of optimality plays a major role in theoretical computer science. Given a computational problem, does there exist a "fastest" algorithm for it? Which proof system yields the shortest proofs of propositional tautologies? Is there a single distribution which can be used to inductively infer any computable sequence? Given a class of optimization problems, is there a single algorithm which always gives the best effcient approximation to the solution? Each of these questions is a foundational one in its area – the first in computational complexity, the second in proof complexity, the third in computational learning theory, and the last in the theory of approximation.

Consider, as an example, the Boolean Satisfiability (SAT) search problem, which asks, given a Boolean formula, for a satisfying assignment to the formula. Since SAT is NP-complete, being able to tell whether the fastest algorithm for SAT runs in polynomial time would imply a solution to the notoriously hard NP vs P problem. However, the possibility remains that we can define an optimal algorithm which we can guarantee to be essentially the fastest on every instance, even if we cannot rigorously analyze the algorithm. In a seminal paper, Leonid Levin (1973) proved that every NP search problem, and in particular SAT, has an optimal algorithm. It is still unknown whether every decision problem in NP has an optimal algorithm.

In general, given a class of computational artefacts (algorithms/proof systems/distributions) and performance measures for each artefact in the class, we say that an artefact is optimal if it matches the performance of every other arte-fact in every case. The main questions about optimality to be discussed in the seminar are: which computational models allow for optimality results, either in terms of optimal algorithms or optimal proofs? In case they do exist, how well do they match the performance of other artefacts in the class? How is the existence of optimal artefacts related to other fundamental theoretical questions, such as complexity lower bounds, effcient learnability or approximability?

There have been a number of important recent results about optimality in various computational settings. Prime examples include optimal proof systems and acceptors under advice or in heuristic settings, surprising relations of optimal proof systems to descriptive complexity and parameterized complexity, hierarchy results in various computational settings, and optimal approximation algorithms for constraint satisfaction problems.

Given these advances it is the right time for a seminar to bring together researchers working on similar questions in different areas, for an exchange of ideas and techniques. Although researchers on optimality share some common methodology – for instance, Kolmogorov complexity – each research community among our prime target areas of proof complexity, logic, computational complexity, and approximations has its own set of techniques and sometimes even different terminology. Our Dagstuhl Seminar will introduce researchers from these different fields to each other's methodology, state-of-the-art advances and open questions, thereby triggering new research collaborations across established research boundaries.