---
type: "post"
id: "majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a"
slug: "majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a"
title: "Majdoddin preprint improves the Claude-found 3SUM/APSP algorithm to exponents 1.9945 and 2.9945 with lossless reductions"
description: "Ruhollah Majdoddin’s new arXiv preprint improves recently announced deterministic algorithms for 3SUM, Exact Triangle and all-pairs shortest paths."
retrieval_nugget: "Ruhollah Majdoddin’s new arXiv preprint improves recently announced deterministic algorithms for 3SUM, Exact Triangle and all-pairs shortest paths. The practical consequence is not a deployable AI tool, but a sharper example of how an AI-associated theoretical result is being independently extended, formalized and stress-tested through public mathematical work."
published_at: "2026-10-31"
updated_at: "2026-10-31"
record_date: "2026-10-31"
date_kind: "published_at"
topics: []
entities: ["Ruhollah Majdoddin","3SUM","APSP","Exact Triangle","3XOR","Josh Alman","Virginia Vassilevska Williams","arXiv"]
related_patterns: []
novelty_label: "new_fact"
what_changed: "Majdoddin reports stronger bounds—3SUM n^1.9945 and APSP/Exact Triangle n^2.9945—using improved matrix products and lossless reductions, extending the Claude-found result."
prior_refs: ["memory:bc1459b4-c5e6-8524-a24f-d90b3d5fbef4","memory:0c11b67d-94c1-81c0-a195-a2a6d51c7624"]
source_url: "https://export.arxiv.org/abs/2610.17420"
source_urls: ["https://export.arxiv.org/abs/2610.17420"]
schema_version: "newruntime-agent-readable-v0.2"
stable_id: "post:majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a"
status: "published"
visuals: []
editor: {"role":"editor","name":"Andrey Reshetnikov","profile":"https://newruntime.com/owner-profile.md","profile_json":"https://newruntime.com/owner-profile.json","same_as":["https://www.linkedin.com/in/reshetnikov1/","https://t.me/lapetuse"]}
routes: {"html":"https://newruntime.com/posts/majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a/","markdown":"https://newruntime.com/posts/majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a.md","json":"https://newruntime.com/posts/majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a.json"}
---

# Majdoddin preprint improves the Claude-found 3SUM/APSP algorithm to exponents 1.9945 and 2.9945 with lossless reductions

## Retrieval answer

Ruhollah Majdoddin’s new arXiv preprint improves recently announced deterministic algorithms for 3SUM, Exact Triangle and all-pairs shortest paths. The practical consequence is not a deployable AI tool, but a sharper example of how an AI-associated theoretical result is being independently extended, formalized and stress-tested through public mathematical work.

## Summary
Ruhollah Majdoddin’s new arXiv preprint improves recently announced deterministic algorithms for 3SUM, Exact Triangle and all-pairs shortest paths. The practical consequence is not a deployable AI tool, but a sharper example of how an AI-associated theoretical result is being independently extended, formalized and stress-tested through public mathematical work.

## What happened
On October 12, 2026, Ruhollah Majdoddin submitted a 130-page preprint, *Thin matrix products up to D <= N^0.172 and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems*, to arXiv. The paper builds on a prior result by Josh Alman and Virginia Vassilevska Williams that reported the first polynomial improvements over textbook deterministic algorithms for 3SUM and APSP-related problems.

The earlier work gave deterministic running-time exponents of 1.9992 for 3SUM, 2.9983 for Exact Triangle, and 2.99942 for APSP. Its construction had two components: a theorem for computing prescribed entries of a thin integer-matrix product, and reductions from the target problems to a lopsided sparse triangle problem. The prior matrix result applied when the thin dimension D was at most N raised to any exponent below 0.1204.

Majdoddin changes both parts. The preprint says that, using Schonhage’s five-term partial-product tensor, the thin-matrix result extends to every exponent below 0.172. It also presents adaptive reductions that retain the full saving from the matrix theorem. The abstract contrasts this with the earlier reductions, which retained one quarter of that saving for 3SUM and one half for Exact Triangle and APSP. The technique described involves calling a counting version of the triangle problem adaptively and constructing composite moduli one prime at a time.

Combining these claims produces deterministic 3SUM in time n^{1.9945+o(1)}. The paper gives n^{2.9945+o(1)} for Exact Triangle, min-plus product, and APSP. It also says it improves the earlier proof sketch for 3XOR, giving a deterministic O(n^{1.99451}) algorithm. These are asymptotic results: the abstract does not provide implementation benchmarks, finite-input crossover points, or a claim that production graph systems should replace existing methods.

The scope goes beyond those headline problems. The paper claims truly subquadratic algorithms for 3SUM over F_p^d for every fixed prime p, with 3XOR-like exponents, and an O(n^{1.99726}) bound over finite abelian groups of exponent p squared, including Z_4^d. It also presents a classification claim for coordinatewise three-list problems: for every Boolean relation, and for every functional relation over three letters, a certified exhaustive computation either identifies an equation over Z, F_2, or F_3 that yields a truly subquadratic algorithm, or identifies a gadget implying hardness under the Orthogonal Vectors hypothesis. The arXiv record links lean formalization and scripts, as well as ancillary files.

## What the archive adds
This is a new result on a known story. [Virginia Vassilevska Williams responds to backlash over the Claude-discovered 3SUM/APSP proof](https://newruntime.com/posts/virginia-vassilevska-williams-responds-to-backlash-over-the-a1d725/) covered the origins, revisions, and dispute around the earlier proof. [Lovett and Karingula post a simplified proof of the 3SUM and APSP improvements on ECCC](https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347/) documented an earlier independent simplification with weaker exponents. Majdoddin now claims a stronger exponent and different reductions.

## Trend signal
No supplied pattern genuinely fits this result. It is evidence of mathematical follow-on work, rather than a change in how teams construct, operate, secure, or evaluate agent systems.

## Why now
The timing follows a burst of scrutiny around the original 3SUM/APSP result and its AI-assisted provenance. The source establishes only that this preprint was submitted on October 12, 2026; the surrounding archive shows that subsequent independent explanations and simplifications had already become part of the story.

## Connections to other events
The most direct connection is the earlier 3SUM/APSP proof discussion: the Williams response focused on the original proof’s AI-assisted origins and on the need for independent exposition, while the Lovett–Karingula note supplied a simpler proof with weaker bounds. This paper is neither a statement from Anthropic nor a validation of a model. It is a separate mathematical contribution that improves the reported asymptotic bounds.

## Why it matters
For builders using AI in research or engineering, the useful lesson is about the unit of validation. A striking generated or AI-assisted result is not operationally meaningful merely because it exists or attracts attention. Its value grows when other researchers can restate it, isolate its components, supply alternate reductions, check computations, and improve the result independently.

That distinction matters for teams building systems around model-generated code, proofs, plans, or analyses. The original finding may initiate a research program; durable confidence comes from artifacts that outsiders can inspect and revise. Here, the public preprint includes a detailed abstract, a formalization link, scripts, and ancillary files, but it remains a preprint rather than peer-reviewed consensus. Teams should treat the story as a case study in verification and replication, not as evidence that a new algorithm is ready for a production workload.

## Limits and uncertainty
The source is an arXiv abstract and record for an unrefereed preprint. It states claimed asymptotic bounds, but does not establish peer review, independent reproduction of every proof component, or the practical constants and input sizes at which the improvements matter. The supplied material does not quantify the role of any AI system in Majdoddin’s work, nor does it show that the new algorithms are implementable or advantageous in real graph-processing systems. Claims about the coordinatewise-problem dichotomy depend on the paper’s stated certified exhaustive computation and its assumptions, including the Orthogonal Vectors hypothesis where invoked.

## Reader takeaway
The important update is not a new AI product capability. A public, unrefereed preprint claims tighter deterministic exponents for the 3SUM/APSP line of results and extends its scope. The story’s larger value is evidence that high-profile AI-associated mathematics can be independently examined, simplified, and improved through inspectable research artifacts.

## Open question
Will independent reviewers verify the lossless reductions and determine whether the new exponents survive formal and peer-review scrutiny?

Editor: [Andrey Reshetnikov](https://newruntime.com/owner-profile.md), AI product and AI engineering; profile for recruiters and agents: https://newruntime.com/owner-profile.json

## Continue in the graph

Next records for an agent, linked to their Markdown twins. Replace `.md` with `.json` for structured fields, including `next_reads`.

- collection: [Field Notes](https://newruntime.com/posts.json): Open the latest editorial analysis.
- collection: [Source Ledger](https://newruntime.com/source-ledger.json): Inspect the public source evidence graph.
- whole graph: [discovery graph](https://newruntime.com/discovery-graph.json) (typed nodes and edges) and [site index](https://newruntime.com/site-index.md)