Two Algorithmic Walls May Have Cracked: The Tiny Exponents Challenging Decades of Computer-Science Assumptions

What happened

A new theoretical-computer-science result claims the first polynomial improvement over the textbook running times for two foundational problems.

In a 76-page preprint posted on 5 October, Josh Alman of Columbia University and Virginia Vassilevska Williams of MIT present a deterministic algorithm that solves 3SUM on n polynomial-size integers in O(n^{1.9992}) time. They also give an algorithm for all-pairs shortest paths, or APSP, on directed n-vertex graphs with polynomially bounded integer weights and no negative cycles in O(n^{2.9995}) time.

This story first reached the Haivian news desk through an X post by researcher Zhao Song. That post was the discovery lead; the authors of the work are Alman and Vassilevska Williams. The claimed results are the authors'; Haivian has not independently checked the 76-page proof.

3SUM asks whether three distinct entries in a collection of numbers add to zero. A standard approach takes roughly quadratic time: as the input grows by a factor of ten, the work grows by about one hundred. APSP asks for the shortest path between every pair of vertices in a weighted graph. Its familiar general bound is cubic.

At first glance, 1.9992 looks almost indistinguishable from 2, and 2.9995 from 3. In practice, these algorithms are not presented as replacements for ordinary implementations. Their importance is mathematical: each exponent is smaller by a fixed constant.

What the evidence shows

For decades, fine-grained complexity has used the 3SUM and APSP hypotheses as foundations for conditional lower bounds. In simplified form, those hypotheses say that no algorithm can solve the relevant general problem in O(n^{2-\varepsilon}) or O(n^{3-\varepsilon}) time for any fixed positive constant \varepsilon.

Logarithmic improvements do not cross that line. A running time such as n^2 / \log n is faster than n^2, but its advantage is not a fixed reduction in the exponent. The new 3SUM bound sets \varepsilon to approximately 0.0008. Tiny or not, it is positive and fixed.

The authors obtain both headline results from a new way to calculate selected entries of a thin matrix product. Given an N\times D matrix multiplied by a D\times N matrix, with D\leq N^{1/18}, their method avoids computing the entire output when only a specified set of entries is needed. For up to N^2/\sqrt D requested positions, they report O(N^2/D^{0.063}) operations.

The construction modifies a rectangular matrix-multiplication method built from an identity due to Arnold Schönhage. Viewed as a graph algorithm, it finds triangles in sparse, highly unbalanced tripartite graphs faster than the earlier barrier. Known reductions then carry part of that saving to Exact Triangle, 3SUM and APSP.

That chain matters. A modest improvement in a carefully chosen primitive can propagate through a network of reductions and overturn several conjectures at once. The paper says the consequences extend to real-valued versions of the hypotheses, zero-weight clique problems and several online matrix-vector conjectures.

What remains uncertain

The paper is a new preprint, not yet the end of community verification. Its central proof is dense, the exponent bookkeeping passes through several reductions, and each transfer preserves only a fraction of the original saving. Independent specialists will need to check the algebra, computational model, parameter ranges and reduction conditions.

The result is also asymptotic. The ratio between n^2 and n^{1.9992} is n^{0.0008}, which grows extremely slowly. Constants, memory requirements and implementation overhead could overwhelm that advantage at any realistic input size. The paper does not provide a benchmark showing that its 3SUM method runs faster than a well-engineered quadratic program on ordinary hardware.

Scope matters too. The stated deterministic 3SUM result concerns polynomially bounded integers, and the APSP result concerns directed graphs with polynomially bounded integer weights and no negative cycles. A headline that says simply “3SUM is solved faster” would discard conditions that belong to the claim.

Why independent scrutiny matters

Fine-grained complexity is unusually sensitive to quantifiers. “For every positive constant,” “for sufficiently large inputs,” “deterministic,” “integer” and “polynomially bounded” are not footnotes. They determine whether a theorem actually crosses the claimed barrier.

That makes the preprint a strong example of what mathematical audit should do. Verification is not just checking the final exponent. It means tracing assumptions through the thin-matrix algorithm, the sparse-triangle interpretation and each reduction; confirming that lower-order factors can be absorbed; and distinguishing theoretical asymptotic improvement from practical speed.

If the proof withstands that scrutiny, the small-looking decimal will mark a genuine change in what computer scientists know is possible. It does not make 3SUM dramatically faster tomorrow. It shows that an exponent long treated as a wall was not a wall after all.

Haivian offers bounded independent audits of mathematical and computational claims. The purpose is not to manufacture certainty around a new result, but to make its assumptions, proof obligations and remaining verification work explicit.