Überraschende Symmetrien für die theoretische Informatik

In dem Projekt, das in der theoretischen Informatik angesiedelt ist, geht es grundsätzlich darum, schnelle Algorithmen zu erforschen und strukturell zu verstehen, wann es solche nicht geben kann. Ausgangspunkt waren Vorarbeiten über mögliche Verbindungen zwischen einer Reihe fundamentaler Fragestellungen in einer Vielzahl von Gebieten, die auf den ersten Blick nichts miteinander zu tun zu haben scheinen.

So zum Beispiel die Frage, ob Zufallszahlen helfen können, schneller zu rechnen, die Suche nach effizienten Schätzmethoden in der Statistik sowie Fragen über die Verschränkung von Quantensystemen, die auf dem Gebiet der Quanteninformation studiert werden. Außerdem geht es um Varianten des sogenannten P-vs-NP-Problems der theoretischen Informatik. Im Kern ist das die Frage, ob es wirklich stimmt, dass es einfacher ist, die Lösung einer Rechenaufgabe zu überprüfen als die Lösung zu finden – wie vermeintlich jedes Kind weiß. Hinzu kommen sogenannte Isomorphismus-Probleme in der Mathematik, die sich um die Frage drehen, wann zwei geometrische Objekte ineinander überführt werden können, und Optimierungsprobleme, die etwa im maschinellen Lernen auftreten, beispielsweise um die Ähnlichkeit zweier Bilder zu berechnen.

Alle diese Themen werden schon seit vielen Jahren von Forschenden in vielen Communities studiert. „Was wir nun beobachtet haben ist – vereinfacht gesagt – dass sich hinter all diesen Fragestellungen Symmetrien verstecken“, beschreibt Prof. Dr. Michael Walter. „Wenn man es schafft, diese offenzulegen, dann liefert einem das einen neuen Ansatzpunkt, um diese schwierigen Fragen anzugehen.“ In diesem Fall lassen sich die Fragen oft als Optimierungsprobleme formulieren, bei denen es darum geht, eine Zielfunktion zu maximieren oder zu minimieren. Im ERC-Projekt "Symmetry and Optimization at the Frontiers of Computation" will er diese Beobachtungen systematisch erforschen.

Das Projekt startet 2022.