TU Dresden mit drei herausragenden Beiträgen auf der FOCS 2026 vertreten

Die Technische Universität Dresden war mit drei Forschungsbeiträgen auf der FOCS 2026 vom 8. bis 11. November in New York vertreten. Das Symposium über Grundlagen der Informatik – IEEE Symposium on Foundations of Computer Science (FOCS) – gilt weltweit als eine der bedeutendsten Konferenzen der theoretischen Informatik. Besonders in den Bereichen Algorithmen und Komplexität setzt die FOCS Maßstäbe. Eine Veröffentlichung dort zählt zu den wichtigsten Auszeichnungen für Forschende auf diesem Gebiet.

In diesem Jahr waren lediglich vier deutsche Universitäten mit insgesamt neun Beiträgen auf der Konferenz dabei – drei davon kamen aus der TU Dresden. Beteiligt waren Forschende aus den Bereichen Algorithmik sowie Algebra und Logik:

- Justin Dallant und László Kozma: „Improved space-time tradeoff for TSP via extremal set  
  systems“ 
- Daniel Neuen und Mitautoren: „Can We Break Fine-Grained and NP-Hardness Barriers if
  We've Seen the Graph Before? The Isomorphic-Priors Model“  
- Andrew Moorhead und Manuel Bodirsky: „Conservative Maltsev Constraint Satisfaction
  Problems“

Der erste Beitrag wurde von Justin Dallant, Postdoktorand an der Professur für Algorithmik, vorgestellt. Er beschäftigt sich mit dem Problem des Handlungsreisenden, bekannt als „Traveling Salesperson Problem“ (TSP). Beim TSP geht es darum, für eine vorgegebene Anzahl von Orten eine möglichst kurze Rundreise zu bestimmen. Das TSP gehört zu den bekanntesten und schwierigsten Problemen der Informatik. Es spielt nicht nur in der theoretischen Forschung eine zentrale Rolle, sondern ist auch für praktische Anwendungen relevant – etwa bei der Planung von Liefer- und Transportrouten, in der Logistik oder bei der Fertigungsplanung.
Die Arbeit von Dallant und Kozma untersucht, wie viel Rechenzeit und wie viel Speicherplatz ein Algorithmus für die Lösung des TSP benötigt. Beide Ressourcen sind für die Leistungsfähigkeit von Algorithmen entscheidend. Der Beitrag identifiziert einen neuen Zusammenhang zwischen diesen beiden Größen und ermöglicht eine besonders gleichmäßige Abwägung zwischen ihnen. Das Ergebnis wird durch eine neue Verbindung zur „extremalen Kombinatorik“ erzielt. 

Der zweite Beitrag von Daniel Neuen und seinen Mitautoren untersucht, was passiert, wenn Algorithmen bereits über relevantes Vorwissen verfügen. Im Mittelpunkt steht dabei das sogenannte „Isomorphic-Priors-Modell“. Es soll einen allgemeinen Rahmen schaffen, um systematisch zu analysieren, wie stark sich Rechenzeiten verkürzen lassen, wenn die Struktur der Daten schon vorher bekannt ist. Ein anschauliches Beispiel wäre ein Verkehrsnetz. Angenommen, die grundlegende Anordnung der Straßen ist bereits bekannt. Die konkreten Orte oder Bezeichnungen können sich unterscheiden, die Verbindungen folgen jedoch demselben Muster. Ein Algorithmus könnte dieses Wissen nutzen, um neue Aufgaben – beispielsweise zur Erreichbarkeit oder zur optimalen Verbindung – schneller zu bearbeiten.

Der Beitrag von Andrew Moorhead und Manuel Bodirsky befasst sich mit sogenannten konservativen Maltsev-Einschränkungs-Erfüllungsproblemen. Viele Aufgaben der Informatik lassen sich auf eine einfache Frage zurückführen: Gibt es eine passende Lösung, die eine Reihe von Bedingungen gleichzeitig erfüllt? Müssen etwa Stundenpläne erstellt, Einsatzorte zugewiesen oder Daten so miteinander verknüpft werden, dass bestimmte Regeln eingehalten werden, handelt es sich um ein sogenanntes Constraint Satisfaction Problem, kurz CSP. Bei einem CSP gibt es Variablen, mögliche Werte und Beziehungen zwischen diesen Werten. Gesucht ist eine Anordnung, die alle vorgegebenen Einschränkungen erfüllt. 

Gemeinsam ist allen drei Arbeiten, dass sie grundlegende Fragen stellen: Wie lassen sich Ressourcen wie Zeit und Speicher optimal einsetzen? Welche Informationen können Algorithmen nutzen? Und welche strukturellen Eigenschaften entscheiden darüber, ob ein Problem effizient lösbar ist?

„Die FOCS ist ein wichtiger Treffpunkt der weltweiten Forschung zu den Grundlagen der Informatik“, sagt Justin Dallant. „Die drei Beiträge zeigen, wie vielfältig die theoretische Informatik an der TU Dresden aufgestellt ist.“

Die Konferenz ist auch aus folgendem Grund denkwürdig: Sie ist vielleicht die letzte Großveranstaltung, bei der die überwiegende Mehrheit der Ergebnisse ohne den Einsatz von KI-Unterstützung erzielt wurde. Da sich generative KI-Tools in den letzten Monaten erheblich verbessert haben, erlebt die Forschung in der theoretischen Informatik und Mathematik derzeit dramatische Veränderungen. Bereits für die nächste große Konferenz, die STOC 2027, hat sich die Zahl der eingereichten Beiträge mehr als verdoppelt, wobei ein erheblicher Teil der erzielten Ergebnisse auf KI-Unterstützung zurückgeht.