A computer scientist broke a limit on mapping network distances that had stood since 1996

A guarantee for estimating distances across networks, set in 1996, now reaches much closer pairs of points than anyone had shown possible. Manoj Gupta, an associate professor at the Indian Institute of Technology Gandhinagar, presented an algorithm at the 66th IEEE Symposium on Foundations of Computer Science that keeps the overall running time while widening the cases where its estimates stay within a factor of two of the truth.

The day in tech, in one email: TLDR is the daily newsletter with links and TLDRs of the most interesting stories in startups, tech and programming.

Get TLDR →

We may earn a commission if you sign up.

The problem is all-pairs shortest paths: given a network of points joined by links, report the shortest route between every pair of points. Exact answers on dense networks take cubic time, so doubling the number of points multiplies the work by roughly eight. That growth rate is why computer scientists have spent decades designing approximations that trade a little precision for a great deal of speed.

The cubic-time wall in all-pairs shortest paths

Cubic cost is why approximation matters. A method that returns a 2-approximation promises an estimate no larger than twice the true distance, and it can run in nearly optimal time instead of cubic time. Approximation schemes differ in what they promise: some bound the error by a fixed factor, some by an additive amount, and some only for pairs beyond a certain distance. Networks that matter in practice, such as road systems, communication links and social graphs, can hold millions of points, and an algorithm that scales badly stops being usable long before the data runs out. The ScienceDaily release from IIT Gandhinagar frames Gupta’s contribution against that backdrop, and the institute’s own news story gives the same account in more detail.

The 1996 landmark method and its blind spot for nearby pairs

Dor, Halperin and Zwick published the earlier method in 1996. It samples a small set of landmark vertices and routes distance estimates through them. For distant pairs a landmark is likely to sit near the shortest path, so the estimate holds. For nearby pairs the closest landmark may lie far off the path, and the detour can break the promise. The release gives an example: a true route of two edges could be estimated as a five-edge route, well beyond the factor-of-two guarantee. The method’s runtime was close to the best that could be hoped for, which made the gap hard to attack, because closing it without slowing things down meant rethinking the sampling itself.

Fast and dependable for distant pairs, then, but silent on close ones. The release says the guarantee did not extend as effectively to nearby vertices.

An air-travel comparison shows the logic. Landmark sampling resembles picking a few hub airports and routing every itinerary through the nearest one. For a transcontinental trip the detour through a hub costs little. For a trip between two neighboring towns, the nearest hub could sit hundreds of miles away and the route balloons. In graph terms, the distant-pair guarantee depends on a landmark lying close to the shortest path, and nearby pairs offer no such assurance.

Multi-scale sampling in Gupta’s algorithm

Instead of one layer of sampled vertices, Gupta arranges samples across several scales, so structure near a pair is captured at a resolution that fits the pair. His paper on arXiv, dated July 26, 2025, describes the algorithm as combinatorial and randomized, with correct results for all pairs with high probability. In the general case the running time is about n to the power 2 plus 1 over k, for pairs only a logarithmic function of k apart. Choosing k equal to the logarithm of n brings the time down to about n squared for pairs at least on the order of log log n apart.

Gupta’s claim, as the institute’s story summarizes it, is that 2-approximate distances can now be computed efficiently for vertex pairs much closer than previously thought possible, without raising the runtime. The SciTechDaily write-up calls the shift an extension of the 1996 sampling idea rather than a replacement. The paper is a single-author work, and it was accepted at FOCS, one of the flagship venues of theoretical computer science.

The runtime has a dial. Turning k down reaches closer pairs at the price of more time, while setting k to the logarithm of n lands at about n squared work, which is still well below the cubic cost of exact answers on dense networks. Because the algorithm is randomized, it can occasionally be unlucky, but the failure probability is kept small enough that the answers are correct for all pairs with high probability.

Theory only, for now

The result is theoretical. ScienceDaily’s account states plainly that it does not establish immediate improvements to specific commercial systems, and it gives no benchmark figures, since the contribution is a proof about guarantees rather than a software release. The conference version carries the DOI 10.1109/FOCS63196.2025.00065, and the symposium ran in December 2025. Real systems also care about memory, hardware and graph structure, none of which a worst-case guarantee addresses on its own.

What remains open is how far the threshold can drop. Gupta’s runtime trade-off ties the closeness of the pairs to the cost, and whether pairs closer still can be covered at nearly optimal time is the question the paper leaves for later work. Other researchers will also want to test whether the multi-scale sampling idea carries over to related approximation problems, such as guarantees other than a factor of two, where the same landmark logic applies.

This article was produced with the assistance of AI and reviewed by Morning Overview editors prior to publication.

The day in tech, in one email: Get TLDR →

We may earn a commission if you sign up.