Switch to German Switch to English

Algorithms and Complexity Group

Prof. Dr. Martin Hoefer
Institute for Computer Science
Goethe University Frankfurt
Robert-Mayer-Strasse 11-15
D-60325 Frankfurt am Main

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

New Paper at COLT 2020 26 May 2020

In the new paper ''A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere'', Marco Schmalhofer shows that a simple variant of the classic perceptron algorithm provides near-optimal guarantees for PAC-learning of halfspaces, where examples are drawn uniformly at random on the hypersphere. The paper was accepted at the 33rd Annual Conference on Learning Theory (COLT 2020), the international top-conference in learning theory.

Two Papers at EC 2020 6 May 2020

Two papers from our group were accepted at the 21st ACM Conference on Economics and Computation (EC 2020), the international top-conference at the intersection of computer science and economics:

DFG Research Group 29 Apr 2020

The German Research Foundation grants funding for a new research group on Algorithms, Dynamics, and Information Flow in Networks. The group is headed by Martin Hoefer, the participating PIs are Petra Berenbrink (Hamburg), Nils Bertschinger, Amin Coja Oghlan, Ulrich Meyer (Frankfurt) and Tobias Friedrich (HPI/Potsdam). The goals are to advance our 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, as well as application domains such as financial markets.