Working Group: Complexity Theory

Fridays, 12:00, seminar room of the algebra department


Content: The goal of this working group is to build a solid background in complexity theory and to prepare the ground for further discussions of current research, concrete problems, and applications in our respective fields. The working group is intended to be interactive, and participants are encouraged to actively contribute to the discussions.


Part I: Background in complexity theory
In the first part, we will focus on learning the necessary background in complexity theory. At the moment, the plan is to cover the following topics (this may change later, and some topics may require more than one meeting).

16.01.26 Preliminary meeting and overview
Marc Kegel
20.02.26 Algorithms and Turing machines
José María Tornero
27.02.26 Undecidable problems and the halting problem
N.N.
06.03.26 Time complexity and polynomial time
N.N.
13.03.26 Deterministic vs. nondeterministic computation
N.N.
20.03.26 Reductions
N.N.
27.03.26 NP-completeness
N.N.
03.04.26 NP-hardness
N.N.
10.04.26 coNP
N.N.
17.04.26 P vs. NP
N.N.

Part II: Beyond the basics
After we have gained a solid understanding of complexity theory, we may move on to discussing current research on algorithms in our respective fields, work on concrete problems, or invite external speakers.


Literature:
[AB] S. Arora, B. Barak,
Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
We will mainly use the first 50 pages.
[K] R. Karp,
Reducibility among combinatorial problems, in: Complexity of Computer Computations, 1972.
Additional references will be added later.



Contact: Marc Kegel