The Gap Shrank to a Constant
A drawing of a short path and a longer detour. Not a figure from the paper.
ScienceDaily recirculated a graph-distance story on 30 October 2026, from IIT Gandhinagar. The headline is about a limit that stood since 1996. The paper behind that write-up is Manoj Gupta, “Improved 2-Approximate Shortest Paths for close vertex pairs,” accepted at the 66th FOCS, 14–17 December 2025, and posted as arXiv:2507.19859 on 26 July 2025. While I was reading the abstract I found the next one. Gupta and Mrigankashekhar Shandilya, submitted 21 July 2026, arXiv:2607.18714, titled with a tilde-O and the word “almost.” I read both abstracts. I did not read the proofs.
Twice as long is the bargain
The job is all-pairs shortest paths on an undirected graph with no edge weights. For every pair of vertices, how many hops is the shortest route. Writing the answer down already takes on the order of n squared numbers, one for each pair, so nobody is going to beat that by more than a log factor and still print the table. A 2-approximation is allowed to answer with a number at most twice the truth. Dor, Halperin, and Zwick, at FOCS 1996, had a near-quadratic algorithm that gave that guarantee only when the true distance was at least on the order of log n. Close pairs were the hole.
The two abstracts disagree about the journal year of that old paper. The 2025 abstract says SICOMP 2000. The 2026 abstract says SICOMP 2001. I am not picking one from a citation I did not open.
Log, then log of log, then a constant
Gupta’s FOCS 2025 algorithm is combinatorial and randomized. For an integer parameter k with log k at least 1, it runs in about n to the power 2 plus 1/k, hiding polylog factors, and the factor-of-two promise holds for pairs at least on the order of log k apart. Set k to log n and the time is near quadratic, and the promise starts at about log log n hops. That is the result the October write-up is describing, in plainer words: closer pairs than 1996, same kind of speed.
The July 2026 abstract says they nearly close the rest. A randomized algorithm, again near quadratic time, again correct with high probability, now promises a 2-approximation for every pair whose true distance is at least some constant c. The constant can be any nonnegative constant they choose to state the theorem for. It is not “every neighbor.” A pair one hop apart can still sit under the line if c is bigger than 1. The abstract does not print the number c. It also drops the purely combinatorial rule. This version mixes those older tricks with fast matrix multiplication.
“Almost” is in the title because the last constant of distance is still exempt, and because the time still hides log factors. Output size says you cannot do much better than n squared. It does not say this algorithm is O of n squared with the logs gone.
Sources: Gupta and Shandilya, arXiv:2607.18714, 21 July 2026; Gupta, arXiv:2507.19859, 26 July 2025, FOCS 2025; recirculation ScienceDaily, 30 October 2026. Proofs unread. The toy’s hop cutoffs are a cartoon of the three thresholds, not the papers’ constants.