Bild © Sina Ettmer / Adobe Stock

Workshop on Algorithms, Complexity and Logic

Theorietag 2026

27th and 28th August 2026 in Lübeck

The 90th Workshop in Algorithms, Complexity, and Logic, commonly known as “Theorietag”, is a joint workshop of the three working groups on Algorithms, Complexity, and Logic of the German Society for Computer Science (GI).

It aims at bringing together researchers from these three core research areas of theoretical computer science and to foster a broad scientific exchange. Moreover, the workshop is a great opportunity for younger researchers to present their work and to connect. There are no formal proceedings, so both published and unpublished work can be presented, without interfering with any past or future publication. A declared goal of the workshop is to enable contact between young and senior scientists.

This workshop has a long tradition and is usually held twice a year. The most recent “Theorietag” was held in Ilmenau in March/April 2026.

Time and Location

Workshop

Social Dinner

Invited Speakers

Markus Hecher Markus Hecher

Centre de Recherche en Informatique de Lens (CRIL), University of Artois, France

Nikolas Mählmann Nikolas Mählmann

Institute of Informatics, University of Warsaw, Poland

Program

Thursday

Time Program
12:00 – 13:00 Lunch in Mensa
13:00 – 13:10 Welcome
13:10 – 14:00 Invited Talk: Markus Hecher (University of Artois): New Insights into the Power of Arithmetic for Counting Complexity
In this talk we show recent insights into fine-grained counting complexity. While it is well-known that the problem of counting the models of a propositional formula in conjunctive normal form (#SAT) or in disjunctive normal form (#DNF) is complete for #P under Turing reductions, it turns out that we need very little computational resources from Turing reductions. Indeed, a single #2DNF call is enough for hardness, as long as we have additional resources well-below P.
14:00 – 14:30 Coffee Break
14:30 – 15:00 Sebastian Berndt (TH Lübeck): A little support goes a long way
A classical approach to design approximation algorithms is to first round the instance and then formulate the rounded problem as integer linear program with a fixed number of variables. The classical approach to solve these integer linear programs is the well-known algorithm due to Lenstra and Kannan. However, for typical parameter settings, this algorithm will often give a double-exponential running time. Already 20 years ago, Eisenbrand and Shmonin showed a significantly faster way to solve such integer programs by showing the existence of very sparse optimal solutions with limited support. This idea and several improvements of these bounds is still the foundation of many of the most efficient approximation schemes. In this talk, we give an overview over several of these bounds and show applications used within in the last years.
15:00 – 15:30 Felix Ohnesorge (Uni Kiel): Practically Efficient Contiguous Monotone Moldable Job Scheduling
In moldable job scheduling, we are provided $m$ identical machines and $n$ jobs that can be executed on a variable number of machines. The execution time of each job depends on the number of machines assigned to execute that job. For the specific problem of \emph{monotone} moldable job scheduling, jobs are assumed to have a processing time that is non-increasing in the number of machines. The previous best-known algorithms are: (1) a Polynomial Time Approximation Scheme (PTAS) with time complexity $\Omega(n^{g(1/\varepsilon)})$, where $g(\cdot)$ is a super-exponential function [Jansen and Thöle ‘08; Jansen and Land ‘18], (2) a Fully Polynomial Time Approximation Scheme (FPTAS) for the case of $m \geq 8\frac{n}{\varepsilon}$ [Jansen and Land ‘18], and (3) a $\frac{3}{2}$ approximation with time complexity $O(nm\log(mn))$ [Wu, Zhang, and Chen ‘23]. We present a new practically efficient algorithm with an approximation ratio of $\approx (1.4593 + \varepsilon)$ and a time complexity of $O(nm \log \frac{1}{\varepsilon})$. Our result also applies to the \emph{contiguous} variant of the problem. In addition to our theoretical results, we implement the presented algorithm and show that the practical performance is significantly better than the theoretical worst-case approximation ratio.
15:30 – 16:00 Klaus Jansen (Uni Kiel): A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Consider a high-multiplicity Bin Packing instance I with d distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime |I|2O(d) for this problem [SODA’14], where |I| denotes the encoding length of the instance I. Although, Jansen and Klein [SODA’17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss [J.ACM’20] whether the doubly exponential dependency on d is necessary. We solve this open problem by showing that unless the ETH fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time |I|^2^{o(d)}. To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding the entire information from a 3-SAT instance with n variables into an ILP with O(log(n)) variables. This result confirms that the Goemans and Rothvoss algorithm is best-possible for Bin Packing parameterized by the number d of item sizes. This is joint work with Felix Ohnesorge and Lis Pirotton.
16:00 – 16:30 Daniel Knaack (Uni Lübeck): Higher-Order Fibonacci Numbers and the Generalized Euclidean Algorithm
TBA
18:00 – 20:00 Dinner at San Marco

Friday

Time Program
09:10 – 10:00 Invited Talk: Nikolas Mählmann (University of Warsaw): Monadic Dependence and Model Checking
In the model checking problem, we are given as input a graph G and a logical formula phi. The goal is to decide whether phi is true in G. Model checking is intractable on general graphs, and the search for the most general graph classes that enjoy fixed-parameter tractable model checking connects the fields of structural graph theory, logic, and parameterized complexity. I will give an introduction to monadic dependence, a notion from model theory that yields a unified perspective on model checking for MSO and FO logic, on both sparse and dense graphs. No background in logic is assumed.
10:00 – 10:30 Coffee Break
10:30 – 11:00 Johannes Tantow (TU Chemnitz): Lexicographic PLS-complete problems
How hard is it to find a local optimum? If we are given a graph and want to find a locally maximal cut–meaning that the number of edges in the cut cannot be improved by moving a single vertex from one side to the other–then just iterating improving steps finds a local maximum since the size of the cut can increase at most |E| times. If, on the other hand, the edges are weighted, this problem becomes hard for the class PLS (Polynomial Local Search). We are interested in optimization problems with lexicographic costs. For Max-Cut this would mean that the edges e_1,…, e_m have costs $c(e_i) = 2^i$. For such a cost function, it is easy to see that finding a global Max-Cut is easy. In contrast, we show that it is PLS-complete to find an assignment for a 4-CNF formula that is locally maximal (when the clauses have lexicographic weights). This result is interesting for two different reasons. Firstly, it offers another starting point for reductions to problems that are lexicographic by definition. We use these results to show a stronger hardness result for the problem of finding a lexicographic local minimum of a string $s \in {0,1}^n$ under the action of a list of given permutations $\pi_1, \dots, \pi_k \in S_{n}$. This was shown to be PLS-complete, which we extend to permutations that form an Abelian group. Secondly, we use it to further investigate the complexity of computing pure $\alpha$-Nash equilibria in congestion games. Using lexicographic 4-SAT, we obtain a simple proof of the PLS-completeness originally shown by Skopalik and Vöcking for step functions and Caragiannis et.al. for polynomials with positive coefficients. This is joint work with Dominik Scheder.
11:00 – 11:30 Sören Möller (Uni Kassel): On the Complexity of Scheme Realisability
We study the complexity of reasoning about influence experiments, a framework for modelling natural science experiments in secondary education as networks of continuous functions (influences) between quantities, constrained by schemes that specify permitted behaviour and range. We consider the Realisability problem: given a scheme, does there exist an influence experiment satisfying it? We show that Realisability is NP-hard via a polynomial reduction from 3CNF-SAT, encoding Boolean truth values as interval constraints on influences, using a diamond-shaped variable order to enforce consistency across occurrences of the same variable, and modelling clause satisfaction via composition of influences. Together with membership in NP, this establishes that Realisability is NP-complete. We conclude by discussing several directions for future work, including the complexity of the problem over a fixed variable set, the related consequence problem, computing witnessing experiments, and extensions of the statement language toward disjunctive and richer constraints.
11:30 – 12:00 Marvin Bergmann (Uni Lübeck): Investigating the complexity of threshold problems for satisfaction probabilities with well-quasi-orderings
In this talk we are investigating well-quasi-orderings as a tool to determine the computational complexity of threshold problems for satisfaction probabilities of constraint satisfaction problems. Given a probability threshold p, we consider the decision problem of determining whether an instance of a constraint satisfaction problem has a satisfaction probability of less than or equal to p. This decision problem has different complexities for different constraint satisfaction problems. We use well-quasi-orderings to find a finite basis for the given decision problem, which then determines the complexity.
12:00 – 12:30 Henry Hartmann (Uni Kiel): Intuitionistic Bounded Arithmetic and Lean
Bounded Arithmetic refers to certain weak subtheories of Peano Arithmetic that restrict the induction axiom. Intuitionistic Bounded Arithmetic uses intuitionistic first-order logic as its basis. Notable about these theories is that they can characterize the polynomial-time computable functions. In this talk we formalize Intuitionistic Bounded Arithmetic in the Lean theorem prover and re-prove some basic results about it and its underlying logic using Lean, thereby verifying their correctness. These are results from my Bachelor’s thesis.
12:30 – 13:30 Lunch in Mensa

Call for Participation

We invite presentations of ongoing or published work in Algorithms, Complexity and Logic, including presentations of Master and PhD projects. There are no formal proceedings.

To register, please send a mail with the following information by 31st July 2026 14th August 2026 (limited late registrations may be possible) to florian.chudigiewitsch@uni-luebeck.de. If you want to attend the Social Dinner, please choose a meal from the menu linked here and type the Meal Number.

I want to register for the Theorietag in Lübeck.

First Name and Surname: ""
Affiliation: ""

I want to give a talk: yes/no
Title of the Talk: ""
Abstract of the Talk: ""

I have the following dietary restrictions: ""
I will attend the Social Dinner: yes/no
Meal Number: ""

Location

The workshop will take place in Lecture Hall “H1”, Building 70 (“Turmgebäude”), at the campus of the University of Lübeck (marked red). You can reach the campus by bus towards either the stop “Technische Hochschule”, “Universitätsstraße”, or “Stephensonstraße” (marked blue).

Campus Plan

Hotels and Directions

Lübeck has many Hotels. We would advise to take a hotel near the main station, old town, or south of the old town, where travel time to the university by public transport takes between 15 to 25 minutes. For example

Organization

Florian Chudigiewitsch (florian.chudigiewitsch@uni-luebeck.de)