Seminar: Complexity Theory

Summer Term 2019

Contact

Phone

work
+49 241 80 21706

Email

E-Mail

Content

The topic of the complexity theory are the principle boundaries of efficient computability. For that the complexity theory questions "inherent dificulties" of algorithmic problems. Therefore the question is not, how efficient the algorithm solves a problem, but how efficient a problem can be solved in general. Efficency will be measured as consumption of ressources, like computation time, used memory, or used bandwith.
Especially the comparison of the different ressource dimensions is tricky. This leads to questions like " Can every memory efficent algorithm be simulated through a time efficent algorithm?" or " Do randomized algorithms in principle work better than deterministic ones?".

Based on the lecture "Computability and Complexity" this lecture is a more in-depth introduction of the central topics of the complexity theory.

Previous Knowledge

Requirment to complete this seminar is a firm grasp of the topics of data structures, algorithms and the computability and complexity. Knowlege from the course "Complexity Theory" is beneficial but not required.

Organization

The dates of the presentations will be set up during the inital meeting.

Instructor

Martin Grohe

Requirements

Each participant of the seminar will work out a 5 sided paper and a 45 minute talk about a algorithmic topic of the complexity theory. With help from original literature and books on the topic the participants will work out their assignments.

Literature

The topics of the seminar will be assigned at the first meeting. Inital litearture to the seminar:

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

External Links