82. Workshop on Algorithms and Complexity (Theorietag)

The Workshop on Algorithms and Complexity (Theorietag) is a recurring event featured by Fachgruppe Algorithmen and Fachgruppe Komplexität of the Gesellschaft für Informatik. A list of past occurrences can be found here.

This Theorietag is supported by DFG Research Group ADYN.

Logo of DFGMap of Campus Westend of GU

The workshop is aimed at all those interested in research in the field of theoretical computer science. The focus is mainly on complexity, algorithms and data structures, as well as parallel and distributed algorithms. 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 will take place offline again for the first time since the beginning of the pandemic.


Wednesday, 08.06.

12:30 - 13:05Check-In and Coffee
13:05 - 13:10Welcome
13:10 - 14:00Invited Talk: The Theory of Practical Graph Isomorphism Solving (Pascal Schweitzer, Darmstadt)
14:00 - 14:25Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks (Marcus Wilhelm, Karlsruhe)
14:25 - 14:50Break
14:50 - 15:15Parameterized Local Search for Max c-Cut (Nils Morawietz, Marburg)
15:15 - 15:40Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings (Johannes Meintrup, Gießen)
15:40 - 16:05The Complexity of Finding Fair Many-to-One Matchings (Tomohiro Koana, Berlin)
16:05 - 16:30Break
16:30 - 16:55Sublinear-Time Probabilistic Cellular Automata (Augusto Modanese, Karlsruhe)
16:55 - 17:20Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems (Markus Schmid, Berlin)
17:20 - 17:45Equation satisfiability for finite solvable groups (Armin Weiß, Stuttgart)
17:45 - 18:30Transition
18:30 - <22:00Dinner

Thursday, 09.06.

08:30 - 09:05Coffee
09:05 - 09:30On Computing Exact Means of Time Series Using the Move-Split-Merge Metric (Jana Holznigenkemper, Marburg)
09:30 - 09:55PPSZ is better than you think (Dominik Scheder, Shanghai)
09:55 - 10:20Counter Claim Augmented Argumentation Frameworks (Yasir Mahmood, Hannover)
10:20 - 10:40Break
10:40 - 11:05Logical Charactarizations of Algebraic Circuit Classes over Rings (Sabrina Gaube, Hannover)
11:05 - 11:30Public Signals in Network Congestion Games (Tim Koglin, Frankfurt)

Sister Event

The final meeting of the DFG Priority Programme “Algorithms for Big Data” will take place directly after this workshop (09.06.-10.06.) at the same venue. Please consider attending that meeting as well.