News
Artikel in der Süddeutschen Zeitung 01 Apr 2026
Im Artikel "So ist es gerecht. Oder?" berichtet die Süddeutsche Zeitung über grundlegende Resultate zu Fair Division und erwähnt dabei auch unsere Forschungen zu Envy-Freeness.
New Paper in Artificial Intelligence 27 Mar 2026
Opinion dynamics model the spread of opinions in social networks. Usually, they capture local trade-offs for agents who adjust their expressed opinions based on internal convictions and peer pressure in their neighborhood. In our paper Opinion Dynamics with Median Aggregation (by Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Marten Maack, Malin Rau, Lisa Wilhelmi) we study a game-theoretic model for opinion dynamics in combination with a global voting mechanism. Apart from the local neighborhood, agents also take the result of a global vote into account. For the important median voting rule, we analyze existence, structure, and computational complexity of equilibrium outcomes. Moreover, we analyze the impact of changes in the susceptability to the voting outcome. The paper has been accepted for publication in Artificial Intelligence, the international top-journal in AI.
Dissertation Defense 17 Mar 2026
Tim Koglin successfully defended his thesis entitled Algorithms for Information and Contract Design in Multi-Agent Network Settings. Congratulations to Dr. Koglin!
New Paper in ACM Transactions on Computation Theory 18 Feb 2026
Trading claims of a bank in distress is described in, e.g., the U.S. and E.U. banking regulations. We formalize this notion in the context of financial networks and study its algorithmic properties. Our paper "Algorithms for Claims Trading" (by Martin Hoefer, Carmine Ventre, Lisa Wilhelmi) characterizes structural properties, provides efficient (approximation) algorithms to compute optimal claims trades, and shows complementing computational hardness results in several variants. Our results reveal an interesting dichotomy -- optimal trading of claims with a common creditor is algorithmically much easier than trading claims with a common debtor. The paper has been accepted for publication in ACM Transactions on Computation Theory.
New Paper in Theoretical Computer Science 12 Feb 2026
In our paper "The Complexity of Blocking All Solutions" (by Christoph Grüne, Lasse Wulf) we consider a general problem of blocking all solutions of some given combinatorial problem with only few elements. This includes, for example, the problem of destroying all Hamiltonian cycles of a given graph by forbidding only few edges; or the problem of destroying all maximum cliques of a given graph by forbidding only few vertices. For a large class of these problems we show that they are Σ2p-complete. Thus, they are substantially more difficult (under standard assumptions in complexity theory) than the underlying base problems (e.g., deciding existence of a Hamiltonian path or finding a maximum clique). The paper has been accepted for publication in Theoretical Computer Science.
Dissertation Defense 9 Feb 2025
Our former group member Komal Muluk successfully defended her thesis entitled Computational Complexity of Graph Orientation, Bilevel and Robust Optimization Problems. Congratulations to Dr. Muluk!
New Paper in Theoretical Computer Science 28 Jan 2026
Debt swaps are a novel local adjustment step to increase the stability and clearing properties of financial networks. In our paper "Dynamic Debt Swapping in Financial Networks" (by Henri Froese, Lisa Wilhelmi, Martin Hoefer) we analyze structural properties and computational complexity of sequential debt swapping. We bound the length of debt swap sequences and examine the hardness of computing states from which no (profitable) debt swap exists. Depending on the payment functions of the banks and the improvement properties of the swaps, we obtain polynomial bounds or establish PLS- and PSPACE-hardness results. The paper has been accepted for publication in Theoretical Computer Science.
New Paper in Algorithms for Molecular Biology 21 Jan 2026
Transcription factors (TFs) are essential in the regulation of gene expression. They can be used to address diseases via manipulation of specific cell functions or pathways. The interplay of TFs and genes can be modeled as a network, in which each edge represents a regulatory influence. A challenge is the identification of a set of TFs with the maximum regulatory influence. In our paper "Probing transcription factor subsets in gene regulatory networks" (by Lukas Geis, Dennis Hecker, Martin Hoefer, Ulrich Meyer, Marcel Schulz) we study finding a set of TFs to maximize the influence on a set of genes as a probing problem in a bipartite graph. We analyze different adaptive and non-adaptive algorithms and test their performance on real-life data to find TFs regulating genes involved in T-cell mediated immunity and lymphoid leukemia. The paper has been accepted for publication in Algorithms for Molecular Biology.
Welcome 1 Jan 2026
Svenja Griesbach joined our group as a PostDoc. Welcome, Svenja!
New Paper at STACS 2026 12 Dec 2025
Our paper "Computing Tarski Fixed Points in Financial Networks" (by Leander Besting, Martin Hoefer, Lars Huth) was accepted at the 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), a leading conference in theoretical computer science.
Sukanya Pandey moves to Durham University 26 Nov 2025
Sukanya Pandey accepted an offer to become a Career Development Fellow at Durham University. Congratulations!
Dissertation Defense 7 Oct 2025
Christoph Grüne successfully defended his thesis entitled Computational Complexity of Problems in Robust, Bilevel and Online Optimization. Congratulations to Dr. Grüne!
Welcome 1 Oct 2025
Jakob Lindner joined our group as a PhD student. Welcome, Jakob!
Best Paper Award at SAGT 2025 3 Sep 2025
We are excited and thankful that our paper "Persuading Agents in Opinion Formation Games" was selected to receive the Best Paper Award at SAGT 2025.
New Paper at SAGT 2025 2 Jul 2025
Our paper "Persuading Agents in Opinion Formation Games" (by Martin Hoefer, Tim Koglin, Tolga Tel) was accepted at the 18th International Symposium on Algorithmic Game Theory (SAGT 2025).
Two Papers at MFCS 2025 27 Jun 2025
Two papers of our group were accepted at the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025).
- Online Knapsack Problems with Estimates
(by Jakub Balaban, Matthias Gehnen, Henri Lotze, Finn Seesemann, Moritz Stocker) - On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
(by Christoph Grüne, Lasse Wulf)
Dissertation Defense 15 May 2025
Marco Schmalhofer successfully defended his thesis entitled Algorithmic Aspects of Fair Division. Congratulations to Dr. Schmalhofer!
New Paper at EC 2025 14 May 2025
Our paper "Welfare and Beyond in Multi-Agent Contracts" (by Gil Aharoni, Martin Hoefer, Inbal Talgam-Cohen) was accepted at the 26th Conference on Economics and Computation (EC 2025), the international top conference at the intersection of economics and computer science.
Click here for older news