ERC Grant für Karl Bringmann

Die Suche nach den Grenzen der Suchgeschwindigkeit - Karl Bringmann erhält bedeutenden Forschungspreis

Karl Bringmann, Senior Researcher am MPI für Informatik, ist vom European Research Council mit einem ERC Grant ausgezeichnet worden, dem europäischen Forschungspreis mit dem höchsten Prestige. Innerhalb der nächsten fünf Jahre stehen ihm jetzt aus seinem ERC Starting Grant 1,5 Millionen Euro zu Forschungsarbeiten über fein-granulare Komplexität / lineare Programmierung zur Verfügung.

Der Begriff fein-granulare Komplexität / lineare Programmierung erscheint beim ersten Lesen beliebig weit vom täglichen Leben entfernt. Die Gutachter bei der europäischen Forschungsagentur sahen das allerdings anders. Das Forschungsthema beschäftigt sich im weiteren Sinne damit, wie schnell ein Computeralgorithmus bei schwierigen Problemen die beste aller möglichen Lösungen finden kann.

Die computergestützte Zusammenstellung von Schicht- oder Stundenplänen ist mittlerweile alltäglich. Hier, wie auch bei anderen Optimierungsaufgaben, kommen Algorithmen zum Einsatz, die dafür sorgen, dass üblicherweise sehr gute Lösungen gefunden werden können, ggf. sogar optimale Ergebnisse. Ähnliches passiert bei der Suche nach Wörtern oder Fragmenten in Texten. Der Entwicklung von schnelleren Suchalgorithmen wurde deshalb seit dem Beginn der Computerzeit große Aufmerksamkeit geschenkt. Die Kenntnis über Grenzen der theoretisch überhaupt möglichen Effizienz solcher Algorithmen vermeidet dann unnötige Bemühungen.

Hier beginnt das Gebiet der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik: Welcher Ressourcenverbrauch (Rechenzeit, Speicherplatzbedarf, ggf. Parallelisierbarkeit) ist mindestens nötig, um ein gegebenes Problem zu lösen.

„Was die Komplexitätstheorie für mich interessant macht, ist die Möglichkeit, bestimmte Grenzen zu finden, die garantiert nicht überwunden werden können. Die Schwierigkeiten des Erkenntnisgewinns sind sehr hoch, die Befriedigung nach einem Resultat aber auch“, umreißt Karl Bringmann seine Motivation: „Selbst wenn es manchmal sehr lange dauert, bis eine bestimmte Hypothese entschieden wird, die Chance diese eine Tür für immer zu öffnen oder zu schließen ist verführerisch.“

Dank des Förderpreises kann Karl Bringmann nun für fünf Jahre mit begabten jungen Mitarbeitern das Thema weiter bearbeiten. Er hofft auf Forschungsergebnisse, die beweisbar, d.h. mathematisch sicher, zeigen, dass es bei bestimmten Problemen keine schnelleren Lösungen geben kann, also ein weiteres Suchen danach von vornherein zum Scheitern verurteilt ist.

Parallel zu Karl Bringmann wurden zwei weitere junge Wissenschaftler mit dem begehrten Preis bedacht, die noch vor kurzem an den Max-Planck-Instituten am Standort Saarbrücken geforscht haben: Zeynep Akata (bis 2017 Postdoc am MPI für Informatik, aktuell Univ. Amsterdam) und Ori Lahav (bis 2017 Postdoc am MPI für Softwaresysteme, aktuell Univ. Tel Aviv).

 

Karl Bringmann
Max-Planck-Institut für Informatik; Algorithms & Complexity
Tel +49.681.9325-1005
kbringma@mpi-inf.mpg.de