How Did Tsinghua Break the 40-Year Shortest-Path Barrier?
Yes, researchers broke the sorting barrier. For four decades, single-source shortest-path (SSSP) algorithms were bottlenecked by the O(m + n \log n) Fibonacci heap sorting limit, but Tsinghua’s STOC 2025 algorithm bypasses continuous priority queue sorting to achieve sub-sorting runtimes on directed graphs. See the complexity timeline and algorithm comparison below →
In a landmark theoretical computer science result awarded the Best Paper Award at the 2025 ACM Symposium on Theory of Computing (STOC), researchers led by Associate Professor Duan Ran from Tsinghua University’s Institute for Interdisciplinary Information Sciences (IIIS) successfully broke the 40-year-old “sorting barrier” in the Single-Source Shortest Paths (SSSP) problem on directed graphs with n vertices and m edges.
Read the original reporting at the South China Morning Post: China’s Tsinghua helps to break 40-year-old maths cap on computer speed.
What was the 40-year-old sorting barrier in computer science?
Since Fredman and Tarjan introduced the Fibonacci heap in 1984 to achieve O(m + n \log n) time, finding the shortest paths from a single source on directed graphs was thought to strictly require sorting all vertices by distance from the source.
Where will this breakthrough have practical applications?
Shortest-path algorithms form the computational backbone for telecommunication packet routing, VLSI chip layout routing, automated drone navigation, and large-scale emergency logistics planning.
Leave a Reply