China’s Tsinghua helps to break 40-year-old maths cap on computer speed

Chinese computer scientists have solved a 40-year-old mathematics bottleneck, a breakthrough that holds significant implications for boosting the performance of hi-tech areas ranging from chip design and telecommunications to drone navigation.

One of the most fundamental problems in theoretical computer science is finding the shortest or most efficient path from one starting point to every other point in a network. Within the academic community, this problem is known as the “single-source shortest-paths” problem (SSSP).

For decades, the most famous and reliable method to overcome this has been Dijkstra’s algorithm, which repeatedly searches for the shortest path for each segment, continuously comparing and sorting the points until reaching its destination. Yet this sorting step poses an unavoidable speed limit.

A new approach devised by a group of young Chinese scientists promises to overcome the barrier, by skipping the sorting process and focusing only on the shortest distance between the most important points, thus greatly reducing calculation time.

The study, led by associate professor Duan Ran’s research team at the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University, was published last month on arXiv, an open-access platform for preprint papers that are yet to be peer reviewed.

This development also won the Best Paper Award at the ACM Symposium on Theory of Computing or STOC, held in Prague in June.