Sidebar
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)
Program
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, secret5@cs.uni-bonn.de
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.
About
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.