Jakub Tětek awarded Best Paper Distinction at FOCS'24
Jakub Tětek, PhD student from BARC, has ben awarded Best Paper Distinction at the prestigious FOCS conference this year.
BARC PhD student Jakub Tětek, who defended his PhD this October, and his co-authors were recently awarded the Best Paper Distinction at FOCS 2024 for their paper:
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Haeupler, R. Hladík, V. Rozhon, R. Tarjan, and J. Tětek
https://focs.computer.org/2024/accepted-papers-with-abstracts/
The paper presents a universally optimal heap for Dijkstra’s single source shortest path algorithm. Developed by Edsger Dijkstra in 1956, the algorithm identifies the shortest path between nodes in a graph and has been a fundamental tool in areas such as network routing, logistics, and robotics. Dijkstra's algorithm was discovered in the 1950s, at a time where almost no computers were around. With the advent to the internet and mobile phones, it is now in everybody's pocket, used by billons of people, often daily, to quickly get from A to B – it is the algorithm that finds shortest travel distances between points in a transportation network, the cornerstone of mobile applications like Google maps.
Dijkstra’s algorithm finds the distances from the source to all other nodes by visiting them in order of increasing distance. The data structure used to find out who is next to be visited is called a heap or a priority queue. The discovery of the award-winning paper is a priority queue that is universally optimal in that it performs best possible on for every graph topology.
The existence of such a universally optimal priority queue is very surprising. The priority queue does not know anything about the graph topology that it is applied to, so you would expect different priority queues to do better on different topologies, but here is a priority queue that beats them all in the sense that it within a constant factor, it is best possible on all topologies.
Tim Roughgarden, a computer scientist at Columbia University, remarked on the significance of this finding: "I can’t imagine a more compelling research paper about a problem we teach students in undergrad algorithms." QUANTA MAGAZINE
Jakub Tětek is a recent PhD graduate of the University of Copenhagen’s Basic Algorithms Research Copenhagen (BARC) center, completed his PhD studies under the supervision of Professor Mikkel Thorup in October 2024.
Tětek’s PhD study has been marked by exceptional achievements and accolades. Over his career, he has earned recognition for his many contributions to algorithmic research and beyond, including the Best Paper honors at both SC 2022 and FOCS 2024, Distinguished Paper award at PODS 2023 and Best Student Paper awards at SODA 2022 and ICALP 2022. These distinctions highlight Tětek’s ability to deliver high-impact results across diverse areas of computer science. In total, he had more than 20 papers accepted for publication by the end of his PhD studies.
As he embarks on the next stage of his career, Tětek’s contributions stand as a testament to the power of rigorous research and the value of foundational algorithmic thinking in solving real-world problems.
