16.03.14 - 21.03.14, Seminar 14121

Computational Complexity of Discrete Problems

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


Computational complexity aims to answer what is efficiently solvable and what is not on various computational models. This means providing upper and lower bounds on the necessary resources such as time, space or communication, and establishing connections among the different models.

There are intricate connections between complexity measures in different computational models. For example circuit size is closely related to computation time, circuit depth and branching program size are closely related to computation space. Breaking the current barriers of our understanding in any of these models would have major consequences in several of the other models as well.

Investigating the connections between the various computational models and subareas of computational complexity has already led to many exciting results. In recent years several novel techniques have been introduced in computational complexity, resulting in a number of breakthroughs, some of which are still actively investigated. Information-theoretic techniques have led to tremendous progress in our understanding of communication complexity, such as new methods to compress interactive communication, new communication protocols that are noise resistant, and a better understanding of so-called direct product questions. This led to progress in understanding the streaming model. Semi-definite programming (a tool originally used in optimization and in the design of approximation algorithms) has led to a tight and very elegant characterization of quantum query complexity. In the area of hardness of approximation, new approaches to prove the Unique Game Conjecture (which is one of the most central open questions in the area) have been suggested.

In the area of separating complexity classes, a recent breakthrough separation of the nondeterministic exponential time NEXP from the bounded-depth circuit class ACC^0 rests on a new technique which derives a lower bound for a non-uniform model from an upper bound on satisfiability in the uniform setting. This technique opens up a new range of possible connections between uniform and non-uniform models.

The goal of the seminar is to bring together the leading researchers working on computational complexity of discrete problems in some of the different subareas and computational models mentioned above. The seminar should serve as a platform for exchange of new ideas among various subareas, with a strong emphasis on new techniques and on the interplay between the different computational models.