http://www.dagstuhl.de/14421

### October 12 – 17 , 2014, Dagstuhl Seminar 14421

# Optimal algorithms and proofs

## Organizers

Olaf Beyersdorff (University of Leeds, GB)

Edward A. Hirsch (Steklov Institute – St. Petersburg, RU)

Jan Krajicek (Charles University – Prague, CZ)

Rahul Santhanam (University of Edinburgh, GB)

## For support, please contact

## Documents

Dagstuhl Report, Volume 4, Issue 10

Aims & Scope

List of Participants

Shared Documents

Dagstuhl Seminar Schedule [pdf]

## Summary

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 efficient 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, which is far beyond the state of our current knowledge.
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 artefact in every case. The main questions about optimality is: for which classes of artefacts and under which assumptions do they exist? 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, efficient 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.

### Organisation of the Seminar and Activities

The seminar brought together 41 researchers from different areas of computer science and mathematics such as computational complexity, proof complexity, logic, and approximations with complementary expertise, but common interest in different notions of optimality. The participants consisted of both senior and junior researchers, including a number of postdocs and a few advanced graduate students.

Participants were invited to present their work and to communicate state-of-the-art advances. Twenty-two talks of various lengths were given over the five-day workshop. Survey talks of 60 minutes were scheduled prior to workshop, covering the three main areas of computational complexity, proof complexity, and approximations. Most of the remaining slots were filled as the workshop commenced. In addition, during two spontaneously organised open problem sessions - one at the very start and the second, longer one near the end of the workshop - the participants posed a number of open problems across the different disciplines covered by the seminar. The organisers considered it important to leave ample free time for discussion.

Three tutorial talks were scheduled during the first two days in order to establish a common background for the different communities from computational complexity, proof complexity, logic, and approximation that came together for the workshop. The presenters and topics were:

- David Steurer: Survey on Approximations and Optimality
- Olaf Beyersdorff: Optimal Proof Systems - a Survey
- Rahul Santhanam: Hierarchies and Lower Bounds via Optimality - a Survey

**License**

Creative Commons BY 3.0 Unported license

Olaf Beyersdorff, Edward A. Hirsch, Jan Krajicek, and Rahul Santhanam

## Classification

- Data Structures / Algorithms / Complexity

## Keywords

- Computational complexity
- Proof complexity
- Computational learning
- Approximation algorithms
- Optimal algorithms
- Optimal proof systems