Switch to German Switch to English


Algorithms and Complexity Group
Institute for Computer Science
Goethe University Frankfurt
Robert-Mayer-Strasse 11-15
D-60325 Frankfurt am Main

Secretary Office:
Teresa Fischer
Institute for Computer Science
Room 116
Tel.: +49 (0) 69 798-28119


New Paper in Journal of Artificial Intelligence Research 24 Nov 2023

New algorithms to compute equilibria in the standard Fisher market model is discussed in our new paper ''Competitive Equilibria with a Constant Number of Chores'' (by Jugal Garg, Martin Hoefer, Peter McGlaughlin, Marco Schmalhofer). When agents have piecewise linear utility functions for goods, computing an equilibrium is known to be a hard problem. Interestingly, the presence of a small number of chores in such markets can make the problem of computing an equilibrium easy. The paper has been accepted for publication in the Journal of Artificial Intelligence Research, a top journal in artificial intelligence.

New Paper at NeurIPS 2023 23 Sep 2023

Our paper ''ε-Fractional Core Stability in Hedonic Games'' (by Simone Fioravanti, Michele Flammini, Bojana Kodric, Giovanna Varricchio) was accepted at the 37th Conference on Neural Information Processing Systems (NeurIPS 2023), the international top-conference in machine learning.

Giovanna Varricchio moves to Università della Calabria 15 Sep 2023

Our group member Giovanna Varricchio accepted an offer to become junior assistant professor (RTD-A) at Università della Calabria. Congratulations!

New Paper in SIAM Journal on Discrete Mathematics 4 Sep 2023

The focus of our paper ''Stochastic Probing with Increasing Precision'' (by Martin Hoefer, Kevin Schewior, Daniel Schmand) are algorithms for probing problems, in which we have a number of choice options (e.g., job candidates, investments, vaccination strategies, etc.). Each option has an unknown quality drawn from a known independent distribution. Before we select an option, we can learn about their quality by testing options adaptively. A test shows whether or not the value is above or below the median value of the conditional distribution (based on outcomes of previous tests). We propose and analyze testing algorithms that provide provably near-optimal performance. The paper has been accepted for publication in SIAM Journal of Discrete Mathematics.

Welcome 1 Sep 2023

Our former secretary Marta Soares moved to a new position in HRZ of Goethe University. We thank her for the excellent service, and we wish her all the best!
At the same time, we welcome Teresa Fischer as the new secretary in our group.

Welcome 1 Sep 2023

We welcome Lars Huth as a new member of our group.

Welcome 1 Aug 2023

We welcome Tolga Tel as a new member of our group.

DFG Research Unit 27 Jun 2023

The German Research Foundation prolongs the financial support for our research unit Algorithms, Dynamics, and Information Flow in Networks (ADYN) until 2026. This will allow us to conduct exciting new research on the understanding of dynamic processes on networks and their relation to efficient algorithms, e.g., in the analysis of spreading processes, distributed network algorithms, network generation models, in the context of static as well as dynamic and temporal networks.

New Paper at ESA 2023 23 Jun 2023

Our paper ''Threshold Testing and Semi-Online Prophet Inequalities'' (by Martin Hoefer, Kevin Schewior) was accepted at the 31st European Symposium on Algorithms (ESA 2023), the European top-conference in design and analysis of algorithms.