TejasviTomar
October 2026 · Preprint

Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?

Tejasvi Singh Tomar

In plain words

For two decades, many speed limits in computing were proved under two assumptions: that the textbook methods are essentially optimal both for finding three numbers in a list that sum to zero and for finding all shortest paths in a network with whole-number link lengths. In October 2026, Alman and Vassilevska Williams disproved both assumptions in their standard forms, with methods whose advantage is small but grows with input size. This paper sorts the main speed limits: most follow from other assumptions that nothing contradicts, a few are false, and the rest have lost their support.

Abstract

In October 2026 Alman and Vassilevska Williams refuted the 3SUM and APSP hypotheses, and with them the Exact Triangle, 3XOR, weighted k-Clique and (min,+)-convolution hypotheses. Their algorithm counts triangles through prescribed edges in lopsided tripartite graphs whose middle part has nε vertices for small ε, and Majdoddin extended its range to every ε < ln 4/(5 ln 5) ≈ 0.17227. Many conditional lower bounds were derived from the refuted hypotheses. We classify the main ones. Most of them were proved through All-Edges Sparse Triangle or offline Set Disjointness on instances that the new algorithms do not reach, namely balanced graphs and lopsided graphs with a larger middle part. We state the hypotheses that these reductions use, among them a family LSTHδ for the natural lopsided instances with middle part nδ, a lopsided form for listing a bounded number of triangles, and degree-bounded, all-nodes and batched forms of the hypothesis for balanced graphs. Most set-disjointness, dynamic-graph and triangle bounds follow from these hypotheses. In contrast, a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes is false, and the trade-offs of Kopelowitz, Pettie and Porat lose their support where they use middle parts below n0.17227. The quadratic bounds for most 3SUM-hard problems in computational geometry, for jumbled indexing and for local alignment over large alphabets are unsupported. We also observe that 3SUM-Indexing now has a data structure with truly subquadratic preprocessing time and truly sublinear expected query time. Finally, we record why the closed-form analysis of the new method stops at ln 4/(5 ln 5), and we use border-rank lower bounds to exclude several natural kinds of base identity that might give a larger range.

A dark chart with a horizontal scale from 0 to 2 and seven labelled rows. A narrow shaded band at the left, up to 0.172, marks where the new algorithms are proved to work. Bars and dots show where each row's hard instances lie, green where the bound survives and orange where it is false or unsupported; the three bars that start at 0 are orange inside the band.
Illustration of the hard instances used by seven groups of the lower bounds classified in the paper. The instances are tripartite graphs with N vertices in each outer part and Nʳ in the middle part; the horizontal axis shows r. The algorithms of Alman and Vassilevska Williams, as extended by Majdoddin, provably cover every r below ln 4/(5 ln 5) ≈ 0.172 (shaded band). Majdoddin reports numerical evidence that the algorithms reach about 0.178 (dashed line) when the queried edges are known in advance and the leaves of the recursion are counted exactly. Bars and dots mark the instances that each bound uses. Orange marks show the parameters at which the offline Set Disjointness bound is false, and those at which the bounds for the online Set Disjointness trade-off and for d-failure connectivity have lost their support. At the green marks, the bounds follow from hypotheses that are still open.