Aktuelles
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!
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.
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!
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.
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).
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.
Hier klicken für nicht mehr ganz so Aktuelles...
New Paper at SAND 2025 28 Mar 2025
Our paper "Dynamic Debt Swapping in Financial Networks" (by Henri Froese, Martin Hoefer, Lisa Wilhelmi) was accepted at the 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025).
In events of distress, an available naval rescue vessel from a home station with the lowest response time is dispatched. But how should rescue vessels be allocated to home stations when their operational availability changes over time due to low tides? In our paper "Rescue Vessel Allocation in Tidal Waters of the North and Baltic Sea" (by Tom Mucke, Alexander Renneke, Finn Seesemann, Felix Engelhardt) we build a mathematical model for this problem. We show that optimizing expected response times to distress calls is NP-hard. However, we provide an Integer Programming formulation and propose two methods of simplifying the model. We then compare the effectiveness of the models in a case study based on real-world data. Results show that the simplified models can be solved to de facto optimality, outperforming the results attained by the full model. The paper has been accepted for publication in Operations Research, Data Analytics and Logistics.
New Paper at AISTATS 2025 24 Jan 2025
Our paper "Independent Learning in Performative Markov Potential Games" (by Rilind Sahitaj, Paulius Sasnauskas, Yiğit Yalın, Debmalya Mandal, Goran Radanovic) was accepted at the 28th International Conference on Artificial Intelligence and Statistics (AISTATS 2025), an international top conference at the intersection of machine learning and statistics.
New Paper at IPCO 2025 22 Jan 2025
Our paper "Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization" (by Christoph Grüne, Lasse Wulf) was accepted at the 26th Conference on Integer Programming and Combinatorial Optimization (IPCO 2025).
New Paper at AAMAS 2025 19 Dec 2024
Our paper "Opinion Dynamics with Median Aggregation" (by Petra Berenbrink, Martin Hoefer, Marten Maack, Malin Rau, Dominik Schallmoser, Lisa Wilhelmi) was accepted as full paper at the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), the international top conference in multi-agent systems.
New Paper at STACS 2025 13 Dec 2024
Our paper "Designing Exploration Contracts" (by Martin Hoefer, Conrad Schecker, Kevin Schewior) was accepted at the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), a leading conference in theoretical computer science.
Visitor 11 Dec 2024
Daniel Schmand is visiting our group Dec 11-13.
Welcome 1 Dec 2024
Sukanya Pandey joined our group as a postdoc. Welcome, Sukanya!
New Paper at SOFSEM 2025 12 Nov 2024
Treasure hunt problems are a variant of graph exploration problems, in which a ''searcher'' needs to find a hidden treasure that is located at a designated vertex in an unknown graph. In our paper ''The Complexity of Graph Exploration Games'' (by Janosch Fuchs, Christoph Grüne, Tom Janßen), we analyze the complexity of different variations of graph exploration and treasure hunt problems. These problems usually come as online problems. We assume that the searcher carries a map of an isomorphic copy of the graph for orientation. We show PSPACE-completeness for the problem of exploring the graph completely or finding the treasure. The paper has been accepted at the 50th International Conference of Current Trends in Theory and Practice of Computer Science (SOFSEM 2025).
The Nash social welfare, given by the product of agent valuations, is a popular objective when assigning indivisble goods to a set of agents. While it has desirable fairness properties, optimization is in general intractable. In our paper ''Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability'' (by Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, Ernest van Wijland) we examine the (in-)tractability in one of the most elementary scenarios, in which additive valuations are based on two non-negative integers p > q. Interestingly, if the ratio p/q (after reduction) is integral or half-integral, we obtain efficient algorithms to find an optimal solution. If p/q has denominator at least 3, the problem becomes intractable. The paper has been accepted for publication in Mathematics of Operations Research, a leading journal in operations research.
Welcome 1 Oct 2024
Finn Seesemann joined our group as a PhD student. Welcome, Finn!
In our paper ''Algorithmic Persuasion with Evidence'' (by Martin Hoefer, Pasin Manurangsi, Alexandros Psomas) we examine the computational complexity of recommendation problems with evidence. This model serves to capture recommendation scenarios, in which a sender (e.g., say, a prosecuter) strives to convince a receiver (judge) to take a certain decision (convict a defendant) - while the receiver would like to take a correct decision (a fair judgement). To do so, the sender, who knows the true state of the world, can present concrete evidence to the receiver, based on which the receiver forms a belief about the state and takes a decision accordingly. In our paper, we provide efficient algorithms for computing an equilibrium in this signaling game. We also give algorithms to compute (near-)optimal solutions and show tight approximation hardness for the bi-level optimization problems that emerge when one of the agents has commitment power. The paper has been accepted for publication in ACM Transactions on Economics and Computation.
Welcome 1 Aug 2024
Rilind Sahitaj joined our group as a PhD student. Welcome, Rilind!
New Paper at WAOA 2024 31 July 2024
Our paper ''Approximating δ-Covering'' (by Tim Hartmann, Tom Janßen) was accepted at the 22nd Workshop on Approximation and Online Algorithms (WAOA 2024).
Website Launch 26 July 2024
Our new website is online.
In our paper ''Delegated Online Search'' (by Pirmin Braun, Niklas Hahn, Martin Hoefer, Conrad Schecker) we study a natural delegation problem, in which a prinicipal (say, a company) outsources the search for a good alternative to an agent (say, a head hunter searching for a job candidate, or a financial agent scanning investment options). The principal specifies criteria for acceptable options in advance (say, qualifications for hiring, or properties of the investment). The agent searches sequentially through the (initally unknown) options in an online fashion and chooses one that is acceptable to the principal and most preferred by the agent. Our contribution is to design efficient algorithms for the principal. Our algorithms set acceptance criteria in order to obtain a good alternative, even though the preferences of principal and agent might be misaligned. The paper has been accepted for publication in Artificial Intelligence, the international top-journal in AI.
A New Beginning 1 June 2024
After more than 7 very successful years at Goethe University, our group will be moving to RWTH Aachen University over the summer. We are excited about the new opportunities and thank everyone for the great time in Frankfurt.
