Malcolm Low | Practical AI, Computing & Quantum Research

Singapore-based practical guides, tutorials and experiments in AI, computing, modelling, simulation, optimisation and quantum computing, with research notes and hands-on workflows.

,

Tsinghua University Breaks 40-Year Computing Math Speed

Yes, Tsinghua broke the sorting barrier. Bottlenecking graph traversal on Fibonacci heaps wastes compute on large networks. See the near-linear SSSP proof →

·

Written by

Quick Answer & Key Insight

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.

Algorithm / Milestone Time Complexity Key Mechanism & Impact
Dijkstra (1959) O(n2) / O(m + n \log n) Greedy priority queue exploration; foundation of graph routing
Fredman & Tarjan (1984) O(m + n \log n) Fibonacci heap amortized bounds; stood as the directed SSSP speed limit for 40 years
Thorup (1999) O(m) (linear) Restricted to undirected graphs with integer edge weights
Duan Ran et al. (STOC 2025) Sub-sorting bound Bypasses full sorting by focusing on critical distance clusters; breaks the 40-year barrier
Table 1: Evolution of Single-Source Shortest Paths (SSSP) algorithmic time complexity.

Read the original reporting at the South China Morning Post: China’s Tsinghua helps to break 40-year-old maths cap on computer speed.

FAQ Frequently Asked Questions

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.

Comments

Leave a Reply