Best Student Paper Award für Fabian Egidy auf der ICALP 2026 in London

Auf dem 53. International Colloquium on Automata, Languages, and Programming (ICALP 2026) in London wurde Fabian Egidy mit dem Best Student Paper Award des Track A (Algorithms, Complexity, Games) ausgezeichnet. Sein Artikel „Recursive Jump Operators and Optimal Proof Systems“ beschäftigt sich mit einer der zentralen offenen Fragen der Beweiskomplexität: Gibt es optimale Beweissysteme, also Strategien, die Aussagen stets mindestens so effizient beweisen wie alle anderen alternativen Strategien?

Der Artikel untersucht die Frage, ob im Falle der Nicht-Existenz solcher optimalen Beweissysteme ein Verfahren existiert, das zu jedem gegebenen Beweissystem algorithmisch ein stärkeres konstruiert. Für alle bisher bekannten Mengen ohne optimales Beweissystem (wie z.b. EXP-vollständige Mengen) zeigt der Artikel, dass solche konstruktiven Verbesserungsverfahren tatsächlich existieren. Für den besonders bedeutenden Fall der Menge aller aussagenlogischen Tautologien, bei dem die Nicht-Existenz optimaler Beweissysteme selbst eine zentrale offene Vermutung ist, beweist der Artikel hingegen, dass ein solcher Zusammenhang nicht mit "aktuell üblichen" (sog. relativierbaren) Methoden gezeigt werden kann. Das Resultat etabliert damit eine neue Beweisbarriere, denn Kandidatenverfahren zur Lösung dieser Frage bedürfen nicht-relativierender Techniken, um sich als konstruktives Verbesserungsverfahren herauszustellen.