Für seine herausragende Dissertation „Graph Sparsification in Distributed and Dynamic Settings“ wurde Tijn de Vos mit dem Heinz Zemanek Preis 2026 ausgezeichnet

Tijn de Vos, Doktorand am Fachbereich Informatik der Universität Salzburg, wurde mit dem Heinz Zemanek Preis ausgezeichnet. Mit diesem von der Österreichischen Computer Gesellschaft (OCG) verliehenen Preis werden alle zwei Jahre bis zu zwei hervorragende Dissertationen auf dem Gebiet der Informatik oder fachverwandter Bereiche ausgezeichnet. Die Arbeit aus dem Bereich der Algorithmik trägt den Titel “Graph Sparsification in Distributed and Dynamic Settings” und wurde von Sebastian Forster betreut, der vor 10 Jahren ebenfalls mit dem Heinz Zemanek Preis ausgezeichnet wurde. Die Preisverleihung fand am 1. Juni im Rahmen des Austrian Computer Science Day 2026 an der TU Wien statt.

Dr. de Vos hat in dieser Arbeit die Komplexität verschiedener Berechnungsprobleme auf Graphen – einem abstrakten Modell für Netzwerke – untersucht. Zentral war dabei die Entwicklung neuartiger Algorithmen mit beweisbar geringeren Laufzeitschranken als der State of the Art. Der Fokus lag dabei auf dynamischen und verteilten Algorithmen, die auf die Verarbeitung massiver Datenmengen ausgelegt sind. Dynamische Algorithmen unterstützen laufende Aktualisierungen der Eingabedaten, die sich zum Beispiel durch die Herstellung neuer Verbindungen in Netzwerken ergeben, wohingegen verteilte Algorithmen auf dezentrale Systeme zugeschnitten sind, in denen die Laufzeit von Algorithmen vom Kommunikationsaufwand zwischen den beteiligten Rechnern dominiert wird. Für das in dieser Arbeit untersuchte verteilte Rechenmodell wurde zudem untersucht, inwiefern sich Quanteneffekte für algorithmische Speed-Ups nutzen lassen, um Eigenschaften großer Quantennetzwerke zu berechnen.

Das zentrale mathematische Konzept hinter diesen Algorithmen wird als “Sparsification” bezeichnet. Dabei wird ein “großer” Eingabegraph durch einen “kleineren” Graph ersetzt, auf dem Algorithmen effizienter ausgeführt werden können. Durch diese Ersetzung ergibt sich aber ein gewisser Informationsverlust, der möglichst gering gehalten werden soll, und in der Regel dazu führt, dass Berechnungsprobleme nicht exakt, sondern nur mit einer gewissen Approximationsgüte gelöst werden. Zusätzlich soll die Ersetzung selbst auch effizient durchführbar sein, damit die Laufzeit nicht von diesem Vorverarbeitungsschritt domininiert wird. Letztendlich ergeben sich mit solchen Methoden also mehrdimensionale Trade-Offs, für die Dr. de Vos problemspezifische “Sweet Spots” gefunden hat.

Die Arbeit wurde im Rahmen der Forschungsprojekte DiAloG (FWF P 32863-N) und DynASoAr (ERC 947702) durchgeführt. Tijn de Vos hat das Doktoratsstudium im November 2024 abgeschlossen und ist mittlerweile als Postdoc an der TU Graz tätig.