💻 computer science

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

This paper presents the first polynomial improvements over textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP) by introducing a novel algorithm for computing sparse entries of matrix products in lopsided graphs, which refutes the 3SUM and APSP hypotheses and yields speedups for numerous related problems.

Original authors: Josh Alman, Virginia Vassilevska Williams

Published 2026-10-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Josh Alman, Virginia Vassilevska Williams

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of computer science, there are problems that have stubbornly resisted improvement for decades, acting as speed bumps for our ability to process information faster. Two of the most famous of these are the "three-sum" problem and the "all-pairs shortest paths" problem. The first asks a simple question: given a list of numbers, can you find three that add up to zero? For a long time, the best way to solve this for a large list of numbers took a amount of time that grew with the square of the list size. The second problem asks for the shortest distance between every single pair of cities in a network of roads. The best known method for this has always taken time that grows with the cube of the number of cities. For years, computer scientists believed these limits were unbreakable, forming a set of rules called "hypotheses" that suggested no algorithm could ever be significantly faster than these textbook methods. These problems are not just abstract puzzles; they underpin everything from mapping software to detecting patterns in complex data, so finding a way to break these speed limits would be a monumental shift in how we compute.

A team of researchers from Columbia University and MIT, working with an artificial intelligence model developed by Anthropic, has now shattered these long-held beliefs. They have discovered a new way to solve these problems that is genuinely faster than the previous best methods. Instead of taking time proportional to the square of the input size for the three-sum problem, their new method solves it in a time that is slightly less than the square. Similarly, for the shortest paths problem, they have reduced the time required to slightly less than the cube of the number of cities. This is not a minor tweak or a trick that only works in special cases; it is a fundamental improvement that applies to a wide range of inputs. By proving that these problems can be solved faster, the researchers have effectively refuted the hypotheses that claimed they could not be.

The secret behind this breakthrough lies in a clever new approach to multiplying matrices, which are simply grids of numbers used to represent data. The researchers focused on a specific type of matrix multiplication where the grids are very thin and long, rather than square. They realized that if you only need to know the answers for a few specific spots in the final result, rather than calculating every single number in the entire grid, you can skip a massive amount of work. They designed an algorithm that acts like a highly efficient filter, ignoring the calculations that would produce answers nobody asked for. This technique was built by modifying an older mathematical identity, a set of rules for combining numbers, to work only on the specific pieces of information that mattered.

The power of this discovery comes from how these different computer problems are connected. In the world of fine-grained complexity, researchers have spent years mapping out how solving one problem helps you solve another. They found that if you can solve the "three-sum" problem faster, you can also solve the "shortest paths" problem faster, and vice versa. The new algorithm acts as a master key. By cracking the code for the specific matrix multiplication problem, the researchers unlocked faster solutions for dozens of other problems that were previously thought to be stuck at their old speeds. This includes finding triangles in networks, checking for specific patterns in data, and optimizing various types of search and sorting tasks.

The team did not just find a theoretical possibility; they provided a concrete, deterministic method that works every time. They also showed that their approach works even when the numbers involved are not just whole integers but real numbers, which are the kind of values used in most real-world scientific calculations. The researchers used a powerful AI tool to help verify their mathematical proofs, ensuring that the logic behind their speedup was sound. This collaboration between human researchers and artificial intelligence highlights a new era in scientific discovery, where machines can help uncover deep mathematical truths that humans might miss.

The implications of this work extend far beyond the specific problems of three-sum and shortest paths. It challenges the idea that some computational limits are absolute. For decades, the community has accepted that certain problems require a specific amount of time to solve, and that trying to go faster was futile. This paper demonstrates that those limits were not walls, but merely ceilings that could be raised with the right perspective. While the new algorithms are currently too complex to be used in everyday software due to the enormous hidden constants in their speed, the proof that they exist changes the theoretical foundation of computer science. It opens the door for future researchers to refine these methods, potentially leading to practical tools that can process massive datasets much more efficiently than ever before. The researchers have shown that even the most stubborn problems can yield to fresh thinking, proving that the boundaries of what is computable are always worth testing.

Technical Summary: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

1. Problem Statement

This paper addresses two fundamental problems in fine-grained complexity theory that have resisted significant improvement for decades:

3SUM: Given $n$ integers of polynomial size, determine if three sum to zero. The standard algorithm runs in $O(n^2)$ time, and the 3SUM Hypothesis posits that no algorithm can solve this in $O(n^{2-\epsilon})$ time for any $\epsilon > 0$ .
All-Pairs Shortest Paths (APSP): Given a directed graph with $n$ vertices and polynomially bounded integer weights, compute the shortest path between all pairs. The standard algorithms (Floyd-Warshall, Johnson) run in $O(n^3)$ time. The APSP Hypothesis posits that no algorithm can solve this in $O(n^{3-\epsilon})$ time.

The paper also targets the Exact Triangle problem (finding a triangle with zero total edge weight in a tripartite graph) and the Directed Unweighted APSP problem, along with a wide variety of problems equivalent to them under fine-grained reductions (e.g., $(\min, +)$ -product, Tree Edit Distance, Zero-Weight $k$ -Clique).

2. Methodology

The core contribution is a new algorithm for computing a prescribed sparse set of entries in the product of two "thin" matrices.

2.1 Thin Matrix Product Algorithm

The authors develop a deterministic algorithm to compute a set $W$ of entries in the product $XY$ , where:

$X$ is an $N \times D$ integer matrix.
$Y$ is a $D \times N$ integer matrix.
$D \le N^{1/18}$ (the matrices are "thin").
$W$ is a set of at most $N^2/\sqrt{D}$ positions.

Key Technical Innovation:
The algorithm modifies Coppersmith's rectangular matrix multiplication algorithm, which itself is built upon a ten-multiplication identity by Sch¨onhage.

Recursive Structure: The algorithm applies Sch¨onhage's identity recursively. Unlike standard matrix multiplication which computes all $N^2$ entries, this algorithm prunes the recursion tree.
Pruning Strategy: It visits only the "leaves" of the recursion tree necessary to compute the entries in $W$ .
Encoding Sharing: The "encoding" phase (linear combinations of input blocks) depends only on the input matrices, not the specific output entries. The algorithm computes these encodings once per input block and shares them across all required computations.
Leaf Analysis: The authors analyze the "order" of leaves in the recursion tree. They prove that while a single output entry requires many leaves, most leaves are shared among many output entries. By carefully balancing the number of leaves of different orders, they show that the total number of leaves required for a sparse set $W$ is significantly smaller than the cost of computing the full product or computing entries individually.

Complexity:
The algorithm computes the entries in $W$ in $O(N^2 / D^{0.063})$ time (with logarithmic factors), which is polynomially faster than the $O(N^2)$ time required to write down the full product or the $O(N^2 \sqrt{D})$ time required to compute the entries individually as inner products.

2.2 Reductions to Graph Problems

The matrix algorithm is applied to the Lopsided All-Edges Sparse Triangle problem. In this problem, one seeks to determine for a set of edges $(a, b)$ in a tripartite graph (with parts $A, B$ of size $n$ and a middle part $M$ of size $D \ll n$ ) whether they lie in a triangle.

Matrix Interpretation: This is equivalent to computing the entries of the product of the biadjacency matrices of the graph at the positions corresponding to the edges in $W$ .
Deterministic Reduction: The paper provides a deterministic reduction from Exact Triangle (on general graphs) to Lopsided All-Edges Sparse Triangle. This involves hashing edge weights modulo a prime chosen deterministically to minimize false positives, followed by a witness search.
Chain of Reductions: Known fine-grained reductions link 3SUM and APSP to Exact Triangle. By composing these reductions with the new algorithm for Lopsided All-Edges Sparse Triangle, the authors derive faster algorithms for the original problems.

3. Key Contributions and Results

3.1 Refutation of Hypotheses

The paper presents the first polynomial improvements over the textbook algorithms for 3SUM and APSP, thereby refuting the 3SUM and APSP hypotheses of fine-grained complexity.

3SUM: Solved deterministically in $O(n^{1.9992})$ time for integers of polynomial size.
APSP: Solved deterministically in $O(n^{2.9995})$ time for directed graphs with polynomially bounded integer weights.
Exact Triangle: Solved deterministically in $O(n^{2.9983})$ time.
Directed Unweighted APSP: Solved deterministically in $O(n^{2+\mu-\epsilon})$ time (where $\mu < 0.5275$ ), refuting the hypothesis that Zwick's algorithm is optimal. This is the first improvement not derived solely from faster rectangular matrix multiplication bounds.

3.2 Real-Valued Variants

Using a reduction by Chan, Vassilevska Williams, and Xu that relies only on comparisons, additions, and subtractions, the authors provide Las Vegas algorithms (randomized with zero error) for the real-valued versions of these problems:

Real 3SUM: Expected time $O(n^{1.998})$ .
Real APSP: Expected time $O(n^{2.998})$ .

3.3 Broader Algorithmic Impact

Through known reductions, the new technique yields polynomial speedups for a wide range of other problems, including:

$(\min, +)$ -product of matrices.
Tree Edit Distance (for polynomially bounded integer costs).
Zero-Weight, Min-Weight, and Max-Weight $k$ -Clique for any constant $k \ge 3$ .
Online Matrix-Vector (OMv) Conjectures: The paper refutes the "hinted" variants of the OMv conjecture (specifically for thin hints) by providing a data structure that preprocesses matrices in sub-quadratic time and answers single-entry queries in sub-linear time relative to the inner dimension.
Knapsack and Approximate Subset Sum: First truly subquadratic algorithms for Unbounded Knapsack and approximation schemes for Subset Sum.

3.4 Data Structure Version

The authors extend the matrix algorithm into a data structure. After preprocessing $X$ and $Y$ in $O(N^2/D^{0.063})$ time, any single entry $(XY)[I, J]$ can be computed in $O(D^{0.437})$ time. This allows for solving problems where the target entries are not known in advance.

4. Significance and Claims

The authors view this work as a "great success for fine-grained complexity."

Reductions as Algorithms: The paper emphasizes that fine-grained reductions, previously used primarily to infer conditional hardness, are also algorithms. A single new technique (the thin matrix product algorithm) can simultaneously speed up a vast web of interconnected problems.
Refuting the Status Quo: The results demonstrate that the "stuck" running times for 3SUM and APSP were not fundamental barriers but rather artifacts of the techniques available at the time.
Limitations and Open Questions:
- The authors note that their techniques do not currently improve CNF-SAT, Orthogonal Vectors, or $k$ -SUM for $k \ge 4$ , as these problems do not reduce to the specific sparse triangle instances solved here.
- The algorithms are algebraic and currently have large hidden constants, making them impractical for immediate real-world use.
- The balanced case of All-Edges Sparse Triangle (where all three parts are size $n$ ) remains unsolved by this technique, leaving the $m^{4/3}$ hypothesis for that specific case intact.
- The paper does not claim to have found the optimal exponents for these problems, noting that further improvements are likely possible through better reductions or refined algebraic identities.

5. Methodology Note on Discovery

The paper explicitly acknowledges that the core algorithm was discovered by Claude, an AI model developed by Anthropic. The authors (Josh Alman and Virginia Vassilevska Williams) worked to understand, simplify, strengthen, and extend the algorithm, derive consequences, and formalize the results. The main results were verified using the Lean 4 proof assistant. The authors take full responsibility for the paper's content and presentation.