ERC Advanced Grant for Martin Grohe

RWTH-Informatikprofessor Martin Grohe erhält für sein Projekt "Symmetry and Similarity" einen Advanced Grant, der als die bedeutendste europäische Forschungsförderung gilt.

 

Graphen sind vielseitige Modelle zur Darstellung komplexer Daten von chemischen Molekülen bis zu sozialen Interaktionen. Bei der Analyse von graph-basierten Daten besteht eine grundlegende Aufgabe darin, Graphen zu vergleichen und ihre Ähnlichkeit auf semantisch sinnvolle und algorithmisch effiziente Weise zu messen. Trotz ihrer Bedeutung in vielen Bereichen wurde Ähnlichkeit von Graphen bislang lediglich in spezifischen Anwendungsbereichen untersucht, teilweise wurden dieselben Techniken immer wieder neu erfunden. Es fehlt eine übergreifende Theorie von Graphähnlichkeit. Dies ist nicht nur eine grundlegende Lücke in der Graphentheorie, sondern es verhindert eine effiziente Nutzung ähnlichkeitsbasierter Methoden für eine Vielzahl von Anwendungen. Ziel dieses ERC-Projekts ist es, eine solche Theorie zu entwickeln und ihre Anwendbarkeit für praxisrelevante Probleme zu demonstrieren.

Ein zentrales Problem in diesem Zusammenhang ist das Graphisomorphieproblem, seit mehr als 50 Jahren eines der bekanntesten offenen Probleme in der Informatik. Es fragt nach einem effizienten Algorithmus, der entscheidet, ob zwei Graphen strukturell identisch sind. Im Rahmen unserer Ähnlichkeitstheorie werden wir dieses Problem aus einem neuen Blickwinkel angehen.

Die Förderung mit dem ERC Advanced Grant richtet sich an führende Forscherinnen und Forscher, die in ihrem Gebiet bereits eine prägende Rolle spielen. Mit einer Dotierung von 2,5 Millionen Euro über fünf Jahre ist der Advanced Grant damit einer der prestigeträchtigsten Forschungsförderung des ERC.