Logic and
Theory of
Discrete Systems

Informatik 7

Complexity Theory

Seminar, WS 2017/18

Topics

Complexity theory is one of the core topics of theoretical computer science; famous open problems such as the P vs. NP problem fall in the realm of complexity theory. It is concerned with the limits of efficient computability. The focus is on the inherent complexity of algorithmic problems: the key question is how efficient the best possible algorithm for the problem is (and not just the best algorithm we know). Efficiency is measured with respect to different resources such as runtime, memory space, communication bandwidth, or more exotic measures such as the amount of nondeterminism or randomness required. A specific challenge is to understand the interaction between these resource measures.

This seminar covers advanced topics in complexity theory, usually focusing on one or two specific branches of complexity theory such as communication complexity, counting complexity, parameterized complexity, derandomisation, etc.

Prerequisites and Requirements

  • Prerequisite for this seminar is a solid foundation in theoretical computer science and a successful completion of the basic courses such as Data Structures and Algorithms and Computability and Complexity. Completion of the course Complexity Theory will be helpful, but is not required.
  • Each participant of the seminar will be assigned a specific topic, usually in form of a research paper or a book chapter. He or she is expected to give a talk (of about 45 min) about it and write a paper (of about 5 pages) summarising it.

Organization

  • Topics will be assigned at the first meeting of the seminar at the beginning of the lecture period in October
  • The seminar will be held in the last week of the semester (exact date will be announced).
  • Instructor: Martin Grohe

References

References for the specific topics will be given in the first meeting. The following textbooks may serve as an introduction to the area.

Computational complexity, Christos H. Papadimitriou;  Addison-Wesley 1994        
Computational Complexity - A Modern Approach, Sanjeev Arora and Boaz Barak  Cambridge University Press    2009        
Theory of Computation, Dexter Kozen; Springer    2006