Top honours for TI researchers
The Institute of Theoretical Computer Science at ETH Zurich is delighted to announce that four of its researchers have recently received some of the most prestigious distinctions in the field. These honours are widely recognised as major milestones in an academic career.
Four researchers from ETH Zurich’s Institute of Theoretical Computer Science have recently been recognised with highly prestigious awards – honours that mark significant milestones in academic careers. The awards highlight not only the outstanding individual achievements of the recipients, but also reflect the vibrant, collaborative and ambitious research culture at the institute.
Congratulations to all awardees!
Christoph Grunau, postdoctoral researcher in Prof. Rasmus Kyng’s group, earned a Best Paper Award at external page FOCS 2024 and the prestigious external page 2025 EATCS Distinguished Dissertation Award.
The honoured paper “Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS” makes major advances in distributed graph algorithms by introducing faster deterministic solutions to three core problems – network decomposition, ruling sets and maximal independent sets – nearly matching known lower bounds.
Richard Hladík, doctoral student in Dr Bernhard Haeupler’s group, and Bernard Haeupler, researcher and Post-Prof at ETH Zurich and faculty at INSAIT, received a Best Paper Award at external page FOCS 2024.
The honoured paper “Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps” shows that Dijkstra’s algorithm, when paired with a specially designed heap, is as fast and efficient as any algorithm can be across all graphs – a property called universal optimality. The authors introduce a new heap that takes advantage of access patterns to speed up operations and prove that it makes Dijkstra’s algorithm optimally efficient, even beyond the worst case.
Tianyi Zhang, postdoctoral researcher in Prof. Rasmus Kyng’s group, received a Best Paper Award at external page STOC 2025. The honoured paper "Vizing's Theorem in Near-Linear Time" solves a long-standing challenge in graph theory: how to quickly assign colors to edges so that no two touching edges share the same color. After decades of slow solutions, the authors introduce a breakthrough algorithm that works much faster than ever before.
About the EATCS Distinguished Dissertation Award
The EATCS Distinguished Dissertation Award is a prestigious award presented annually by the European Association for Theoretical Computer Science (EATCS). It honours outstanding doctoral theses in the field of theoretical computer science with the aim of recognising and promoting excellent research at an early stage.
About FOCS and STOC
FOCS (IEEE Symposium on Foundations of Computer Science) is one of the two top-tier annual conferences in theoretical computer science, alongside STOC (Symposium on Theory of Computing). These conferences are known for featuring breakthrough results in algorithms, complexity theory, cryptography, distributed computing and related areas.