GI-Theorietag 2022

83rd Workshop on Algorithms and Complexity

The 83rd Theorietag will take place in Bonn. This workshop is organized by the Algorithms and Complexity group of the University of Bonn and supported by the Gesellschaft für Informatik and the Hausdorff Center for Mathematics.

The workshop has no formal proceedings. Ongoing work as well as published work can be presented.

Dates: 10th and 11th of November 2022 (afternoon + morning)

Location: Lipschitz-Saal, Endenicher Allee 60, 53115 Bonn

Invited Speaker: Karl Bringmann (Saarland University and MPI)


Thursday, November 10, 2022

Time Speaker Title Social Event
12:30 - 13:00 Registration
13:00 – 13:25 Tim Hartman Continuous Facility Location on Graphs
13:25 – 13:50 Stefan Walzer Simple Linear Set Sketching
13:50 – 14:15 Meike Neuwohner The Limits of Local Search for Weighted k-Set Packing
14:15 - 14:45 Coffee Break
14:45 – 15:10 Jesse van Rhijn Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
15:10 – 15:35 Niklas Jost Approximation Algorithms for Hub Location Problems
15:35 – 16:00 Kelin Luo Package Delivery Using Drones with Restricted Movement Areas
16:00 - 16:15 Coffee Break
16:15 – 16:40 Anna Arutyunova The Price of Hierarchical Clustering
16:40 – 17:05 Abhiruk Lahiri Reconfiguring shortest paths in graphs
17:05 – 17:30 Andreas Padalkin Reconfigurable Circuits in the Geometric Amoebot Model
17:30 - 17:45 Break
17:45 – 18:10 Daniel Mock Evaluating Restricted First-Order Counting Properties on
Nowhere Dense Classes and Beyond
18:10 – 18:35 Timon Barlag Logical Characterizations of algebraic circuit classes over rings
18:35 - Open end Dinner

Friday, November 11, 2022

Time Speaker Title Social Event
08:00 - 09:00 Breakfast
09:00 – 10:00 Karl Bringmann Hardness of Approximation in P: Fine-Grained
Complexity of Graph Distance Approximation
10:00 - 10:15 Break
10:15 – 10:40 Martin Nägele Congruency-Constrained Optimization
10:40 – 11:05 Arindam Biswas Sublinear-Space Approximation Algorithms for Hitting Set
11:05 – 11:30 Ekin Ergen Farthest Insertion Heuristic for TSP
11:30 - 12:00 Coffee Break
12:00 – 12:25 Benedikt Kolbe On the computational geometry of hyperbolic surfaces
12:25 – 12:50 Felix Tschirbs Dynamic complexity of regular languages: Big changes, small work
12:50 – 13:15 Kevin Mann Minimal Roman Dominating Functions: Extensions and Enumeration

The whole program including the abstracts for each talk can be found here

Contact & Registration

Email: Christiane Andrade,

If you would like to attend: Please register by sending an e-mail to the above address until 21 October 2022.

If you plan to give a talk: Please include in your email (until 21 October 2022) the title and abstract of your talk (preferably send the latex source code). If there is a corresponding manuscript available online, please include a link to the manuscript. Each talk should be in English and about 20 minutes long (followed by a 5-minute discussion round).

In any case, participation is free of charge.


The Theorietag on Algorithms and Complexity is a recurring event featured by the Fachgruppe Algorithmen and Fachgruppe Komplexität of the Gesellschaft für Informatik. A list of previous iterations of this event can be found here.

Page Tools