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 No talk
06.03.26 Undecidable problems and the halting problem
Marc Kegel
13.03.26 Undecidable problems in algebra
Owen Garnier
20.03.26 Undecidable problems in topology
Marc Kegel
27.03.26 No talk
03.04.26 No talk
10.04.26 Polynomial time and deterministic vs. nondeterministic computation
Francisco Félix Lara Martín
17.04.26 The class of NP problems
N.N.
24.04.26 Reductions and NP-completeness
N.N.
01.05.26 NP-hardness
N.N.
08.05.26 coNP
N.N.
15.05.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