INSAIT scientists achieved a breakthrough in the area of graph algorithms and were awarded a best paper award at FOCS’24, a top conference in algorithms and theory! The work is a collaboration between researchers at INSAIT, ETH Zurich and Princeton. The best paper award was received amongst 133 accepted papers at FOCS’24.
The result is one of the hottest and most discussed topics in computing in the last few days. It is also the 1st time in 65 years that a Bulgarian organization has accepted papers at FOCS!
The paper demonstrates surprising new possibilities of Dijkstra’s nearly 70-year-old classic algorithm, taught in all introductory algorithm classes and the basis of some of the most used applications in the world – GPS, route planning, etc. The new mechanism shows how the algorithm can be used to compute the most direct route optimally, as quickly as possible, when faced with any graph task (e.g. logistics, crisis response, etc.), without any deviation!
Congratulations to all authors: Dr. Bernhard Haeupler (INSAIT and ETH), Richard Hladík (ETH, visitor at INSAIT), Dr. Václav Rozhoň (INSAIT), Dr. Jakub Tětek (INSAIT), and prof. Robert Tarjan (Princeton), Turing Award winner (equivalent to Nobel for Computing).
Except this work, INSAIT researchers participate with 4 accepted publications at FOCS’24, including a paper by Dr. Tomasz Kociumaka, a new faculty in theory and algorithms who recently joined INSAIT from Max-Planck. Congrats to all!
Link to the paper: https://arxiv.org/pdf/2311.11793
Link to a Quanta Magazine article explaining the result: https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/