81. Workshop über Algorithmen und Komplexität (Theorietag)

81. Workshop über Algorithmen und Komplexität (Theorietag)

The workshop is aimed at all those interested in research in the field of theoretical computer science. The focus is especially on complexity, algorithms and data structures, as well as parallel and distributed algorithms.

The relevant topics include, in addition to algorithmic and complexity-theoretic issues, in particular algorithm theory, algorithm engineering, applied algorithms, parallel/partial algorithms, complexity classes, hierarchies, lower and upper complexity bounds for special problems, structural issues, equivalence studies, one-way and trapdoor functions, cryptography, interactive proof systems, complexity of logical decision problems, logical-descriptive complexity classes, parameterised complexity, Kolmogorov complexity, non-uniform computational models (special automata, circuits, branching programs, formulas).

Participation in the workshop does not constitute a publication, so both ongoing and completed work can be presented. A declared goal of the workshop is to enable contact between young and senior scientists.

The workshop is part of INFORMATIK 2021, the 51st Annual Conference of the German Informatics Society (Gesellschaft für Informatik e.V.) which is virtually organised from 27th of September to 1st of October 2021.

The workshop is scheduled on 28th of September 2021.

There will be an invited talk with the title "On distributed algorithms in Digitalized Energy Systems" given by Prof. Dr.-Ing. Astrid Nieße (University Oldenburg) that has the context of energy informatics.

If you want to contribute a talk, please send title and abstract to Arne Meier by E-Mail before 21.09.2021. The length of each talk will be 30 minutes.

Please note that you need to purchase a ticket to attend the workshop for INFORMATIK 2021 ( If you are a student, you can also get free tickets by participating in the Digital Innovation Challenge ( 

The workshop will take place virtually (Access via registration link of the GI Annual Conference).

The conference room of the workshop is called "Sophie Wilson".

The workshop is organised by Heribert Vollmer and Arne Meier.

9:20Gathering in Conference Room Sophie Wilson
9:25Welcome (Arne Meier)
9:30Invited Talk: On distributed algorithms in Digitalized Energy Systems (Astrid Nieße, U Oldenberg)
10:30Break (30m)
11:00Placing Green Bridges Optimally, with a Multivariate Analysis (Leon Kellerhals, TU Berlin)
12:00Lunch Break (1h30m)
13:30Computational Complexity of Deciding Provability in Linear Logic and Its Fragments (Florian Chudigiewitsch, U Hannover)

Short Break (10m)

14:30Covering Sets of Point Sets by Disjoint Convex Sets (Elias Dahlhaus, TU Darmstadt)
15:20Short Break (10m)
15:30The Parameterized Complexity of Multistage 2-Coloring (Pascal Kunz, TU Berlin)
16:20Closing (Heribert Vollmer)