Breakthroughs in Computational Complexity: Subquadratic 3SUM and Subcubic APSP

This technical report summarizes the findings of the paper "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs," authored by Josh Alman and Virginia Vassilevska Williams.

🚀 The Core Achievement

The authors have achieved the first-ever polynomial improvements over the standard "textbook" algorithms for two fundamental problems in computer science: 3SUM and All-Pairs Shortest Paths (APSP).

Performance Benchmarks

The following table outlines the new deterministic time complexities achieved for these problems:

---

📉 Impact on Theoretical Hypotheses

By leveraging established reductions, this research effectively validates refutes several long-standing conjectures and hypotheses. The following are no longer held as absolute bounds:

• The real-valued 3SUM hypothesis
• The real-valued APSP hypothesis
• The Exact Triangle hypothesis
• Zero-Weight $k$-Clique hypotheses
• Three rectangular hinted Online Matrix--Vector conjectures (proposed by van den Brand, Nanongkai, and Saranurak)

Note: These results also provide polynomial speedups for a wide array of other related computational problems.

---

🛠️ The Technical Engine: Thin Matrix Products

The foundation of these breakthroughs is a novel algorithm designed for thin matrix products.

Mathematical Definition

Let's define the parameters of the operation:

• Let $X$ be an integer matrix of size $N \times D$.
• Let $Y$ be an integer matrix of size $D \times N$.
• Constraint: $D \le N^{1/18}$.
• Let $W$ be a set of target positions where $|W| \le N^2/\sqrt{D}$.

The algorithm computes the entries $(XY)[I,J]$ for all $(I,J) \in W$ with a complexity of: $\text{Time} = O\left(\frac{N^2}{D^{0.063}}\right)$

This is significantly more efficient than the naive approach of computing $N^2/\sqrt{D}$ individual inner products or simply writing out the entire resulting matrix $XY$.

Implementation Logic

The authors developed this by adapting a specific variant of Coppersmith's rectangular matrix multiplication. Specifically, they utilized:

1. A ten-multiplication identity derived from Schönhage.
2. A modification to ensure the algorithm only performs operations essential for the entries specified in $W$.

# Conceptual representation of the target computation
def compute_thin_product(X, Y, W):
    # X: N x D, Y: D x N, W: set of (i, j)
    # Optimized via modified Coppersmith/Schönhage identity
    results = {}
    for (i, j) in W:
        results[(i, j)] = optimized_inner_product(X[i], Y[:, j])
    return results

---

🕸️ Graph Theory Interpretation

When viewed through the lens of graph theory, this algorithm solves the All-Edges Sparse Triangle problem in truly subquadratic time. This applies specifically to sparse lopsided tripartite graphs meeting these criteria:

• Two partitions contain $n$ vertices.
• One partition contains $n^{\varepsilon}$ vertices.
• The exponent $\varepsilon$ must be $< 0.12$.

Reduction Pipeline

The logical flow of the discovery can be visualized as follows:

---

📦 Additional Contributions

Beyond the primary algorithms, the authors introduce a data structure version of their work. This allows for the querying of single entries of the product $XY$ without requiring the set $W$ to be known in advance.

Document Metadata

• arXiv ID: 2610.06783
• Submission Date: October 5, 2026
• Length: 76 pages
• Categories: cs.DS (Data Structures and Algorithms), cs.CC (Computational Complexity)