For his outstanding dissertation “Graph Sparsification in Distributed and Dynamic Settings,” Tijn de Vos has been recognized with the Heinz Zemanek Award 2026.

Tijn de Vos, a former doctoral researcher at the Big Data Algorithms Group at the University of Salzburg, has been recognized with the Heinz Zemanek Award. This award, sponsored by the Austrian Computer Society (OCG), is given every two years to up to two outstanding dissertations in the field of computer science or related areas. The awarded work is titled “Graph Sparsification in Distributed and Dynamic Settings” and was supervised by Sebastian Forster, who himself received the Heinz Zemanek Award 10 years ago. The award ceremony took place on June 1 as part of the Austrian Computer Science Day 2026 at TU Wien.

Dr. de Vos investigated the complexity of various computational problems on graphs – an abstract model for networks. A central aspect of the work was the development of novel algorithms with provably lower running time bounds than the state of the art. The focus was on dynamic and distributed algorithms designed to handle massive input data. Dynamic algorithms support ongoing updates to input data, such as the formation of new connections in networks, while distributed algorithms are tailored to decentralized systems in which the running time is dominated by communication costs between participating computers. For the distributed computational model studied in this work, the extent to which quantum effects can be used for algorithmic speed-ups to compute properties of large quantum networks was also investigated.

The central mathematical concept behind these algorithms is called graph sparsification. This involves replacing a “large” input graph with a “smaller” one on which algorithms can be executed more efficiently. However, this replacement leads to some loss of information, which must be kept as small as possible and typically results in computational problems being solved not exactly, but with a certain approximation guarantee. In addition, the replacement itself must be computationally efficient so that it does not dominate the overall running time. Ultimately, these methods involve multidimensional trade-offs for which Dr. de Vos identified problem-specific “sweet spots.”

The work was carried out within the research projects DiAloG (FWF P 32863-N) and DynASoAr (ERC 947702). Tijn de Vos completed his doctoral studies in November 2024 and is currently a postdoctoral researcher at TU Graz.