Alman and Vassilevska Williams's preprint reports the first truly subquadratic 3SUM (O(n^1.9992)) and truly subcubic APSP (O(n^2.9995)) algorithms — attributing the core thin-matrix-product algorithm to an Anthropic research model with Lean-formalized theorems — and expert acceptance of both the results and the AI-origin attribution would establish frontier models as originators of landmark theoretical-CS advances.

Open article · Retrieved 2026-10-06T07:24:15.179319+00:00

# Computer Science > Data Structures and Algorithms

**arXiv:2610.06783** (cs)

[Submitted on 5 Oct 2026]

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

Authors:[Josh Alman](https://arxiv.org/search/cs?searchtype=author&query=Alman,+J), [Virginia Vassilevska Williams](https://arxiv.org/search/cs?searchtype=author&query=Williams,+V+V)

View a PDF of the paper titled Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, by Josh Alman and Virginia Vassilevska Williams

[View PDF](https://arxiv.org/pdf/2610.06783)
[HTML (experimental)](https://arxiv.org/html/2610.06783v1)
> Abstract:We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems.
>   
> All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

|  |
| --- |
| Comments: |
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC) |
| Cite as: | [arXiv:2610.06783](https://arxiv.org/abs/2610.06783) [cs.DS] |
|  | (or  [arXiv:2610.06783v1](https://arxiv.org/abs/2610.06783v1) [cs.DS] for this version) |
|  | <https://doi.org/10.48550/arXiv.2610.06783> Focus to learn more  arXiv-issued DOI via DataCite (pending registration) |

## Submission history

From: Josh Alman [[view email](https://arxiv.org/show-email/6de32e58/2610.06783)]

Full-text links:

## Access Paper:

View a PDF of the paper titled Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, by Josh Alman and Virginia Vassilevska Williams

- [View PDF](https://arxiv.org/pdf/2610.06783)
- [HTML (experimental)](https://arxiv.org/html/2610.06783v1)
- [TeX Source](https://arxiv.org/src/2610.06783)

[license icon](http://creativecommons.org/licenses/by/4.0/ "Rights to this article")

### Current browse context:

cs.DS

[< prev](https://arxiv.org/prevnext?id=2610.06783&function=prev&context=cs.DS "previous in cs.DS (accesskey p)")
  |   
[next >](https://arxiv.org/prevnext?id=2610.06783&function=next&context=cs.DS "next in cs.DS (accesskey n)")

[new](https://arxiv.org/list/cs.DS/new)
 | 
[recent](https://arxiv.org/list/cs.DS/recent)
 | [2026-10](https://arxiv.org/list/cs.DS/2026-10)

Change to browse by:

[cs](https://arxiv.org/abs/2610.06783?context=cs)  
[cs.CC](https://arxiv.org/abs/2610.06783?context=cs.CC)

### References & Citations

- [NASA ADS](https://ui.adsabs.harvard.edu/abs/arXiv:2610.06783)
- [Google Scholar](https://scholar.google.com/scholar_lookup?arxiv_id=2610.06783)
- [Semantic Scholar](https://api.semanticscholar.org/arXiv:2610.06783)

export BibTeX citation
Loading...

## BibTeX formatted citation

×

loading...

Data provided by:

### Bookmark

[BibSonomy](http://www.bibsonomy.org/BibtexHandler?requTask=upload&url=https://arxiv.org/abs/2610.06783&description=Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs "Bookmark on BibSonomy")
[Reddit](https://reddit.com/submit?url=https://arxiv.org/abs/2610.06783&title=Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs "Bookmark on Reddit")



Bibliographic Tools

# Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer *([What is the Explorer?](https://info.arxiv.org/labs/showcase.html#arxiv-bibliographic-explorer))*

Connected Papers Toggle

Connected Papers *([What is Connected Papers?](https://www.connectedpapers.com/about))*

Litmaps Toggle

Litmaps *([What is Litmaps?](https://www.litmaps.co/))*

scite.ai Toggle

scite Smart Citations *([What are Smart Citations?](https://www.scite.ai/))*

Code, Data, Media

# Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv *([What is alphaXiv?](https://alphaxiv.org/))*

Links to Code Toggle

CatalyzeX Code Finder for Papers *([What is CatalyzeX?](https://www.catalyzex.com))*

DagsHub Toggle

DagsHub *([What is DagsHub?](https://dagshub.com/))*

GotitPub Toggle

Gotit.pub *([What is GotitPub?](http://gotit.pub/faq))*

Huggingface Toggle

Hugging Face *([What is Huggingface?](https://huggingface.co/huggingface))*

ScienceCast Toggle

ScienceCast *([What is ScienceCast?](https://sciencecast.org/welcome))*

Demos

# Demos

Replicate Toggle

Replicate *([What is Replicate?](https://replicate.com/docs/arxiv/about))*

Spaces Toggle

Hugging Face Spaces *([What is Spaces?](https://huggingface.co/docs/hub/spaces))*

Spaces Toggle

TXYZ.AI *([What is TXYZ.AI?](https://txyz.ai))*

Related Papers

# Recommenders and Search Tools

Link to Influence Flower

Influence Flower *([What are Influence Flowers?](https://influencemap.cmlab.dev/))*

Core recommender toggle

CORE Recommender *([What is CORE?](https://core.ac.uk/services/recommender))*

- Author
- Venue
- Institution
- Topic


About arXivLabs

# arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? [**Learn more about arXivLabs**](https://info.arxiv.org/labs/index.html).

[Which authors of this paper are endorsers?](https://arxiv.org/auth/show-endorsers/2610.06783) |
Disable MathJax ([What is MathJax?](https://info.arxiv.org/help/mathjax.html))