ERC Grant Überraschende Symmetrien für die theoretische Informatik

Auf der Suche nach schnellen Algorithmen ist der Informatiker Prof. Dr. Michael Walter auf überraschende Gemeinsamkeiten gestoßen: Eine ganze Reihe von Forschungsproblemen, die vermeintlich wenig miteinander zu tun haben, lassen sich auf Symmetrien und Optimierungsprobleme zurückführen. Diese Entdeckung bietet einen neuen Blickwinkel auf bekannte offene Fragen der Informatik und Mathematik. Dem geht der Inhaber des Lehrstuhls für Quanteninformation der RUB künftig mit Unterstützung des European Research Council (ERC) nach. Sein ERC Starting Grant „Symmetry and Optimization at the Frontiers of Computation” startet am 1. Mai 2022 und hat eine Laufzeit von fünf Jahren.

Ein bunter Strauß von Fragen

Das geförderte Projekt ist in der theoretischen Informatik angesiedelt. „Es geht also grundsätzlich darum, schnelle Algorithmen zu erforschen und strukturell zu verstehen, wann es solche nicht geben kann“, erklärt Michael Walter. Ausgangspunkt waren eine Reihe von Vorarbeiten, in denen er gemeinsam mit internationalen Kolleginnen und Kollegen mögliche Verbindungen zwischen einer Reihe fundamentaler Fragestellungen in einer Vielzahl von Gebieten bemerkt hat, die auf den ersten Blick nichts miteinander zu tun zu haben scheinen.

„Dazu gehört beispielsweise die Frage, ob Zufallszahlen helfen können, schneller zu rechnen“, so Walter. „Das ist eine der grundlegenden offenen Fragen der Informatik.“ Andere Beispiele sind 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ß“, erklärt Walter. 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.

Ein neuer Blickwinkel könnte der Schlüssel sein

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 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. „Das ist durchaus unerwartet, denn die meisten der oben genannten Fragestellungen scheinen überhaupt nichts mit Optimierung zu tun zu haben“, so Walter. „Nichtsdestotrotz konnten wir in Spezialfällen bereits zeigen, dass der neue Blickwinkel den Schlüssel für schnelle Algorithmen und neue strukturelle Einsichten bieten kann.“

Optimierung in gekrümmten Räumen

Im ERC-Projekt will er diese Beobachtungen systematisch erforschen. Theoretisch sind die dabei auftretenden Optimierungsprobleme noch nicht gut verstanden. „Grund dafür ist, dass es hier um Optimierung in gekrümmten Räumen geht, die sehr unintuitive Eigenschaften haben“, erklärt Michael Walter. „Wir möchten das neue Optimierungsparadigma auf ein solides theoretisches Fundament stellen, universelle Methoden entwickeln, und den neuen Ansatz dann auf theoretische und praktische Fragestellungen wie die oben erwähnten anwenden. Dabei hoffen wir insbesondere auf effiziente numerische Algorithmen für herausfordernde algebraische Probleme und Fortschritte bei schwierigen Fragen der Komplexitätstheorie, aber auch auf neue Anwendungsmöglichkeiten für Quantencomputer. Insgesamt ist unser Ziel, nachhaltig und fachbereichsübergreifend neue Einsichten zu erlangen.“