The paper's methodology section says an Anthropic employee initially asked an internal research model to study a cryptographic question based on average-case Zero-k-Clique.
Alman and Vassilevska Williams report deterministic algorithms solving 3SUM on polynomial-size integer inputs in O(n^1.9992) time and APSP with polynomially bounded integer weights in O(n^2.99942) time in their word-RAM formulation, together with related improvements for Exact Triangle, min-plus product and zero-weight k-Clique. The paper states that these are the first truly subquadratic and truly subcubic algorithms in the corresponding settings and that they refute the standard 3SUM and APSP hypotheses used in fine-grained complexity.
The paper's methodology section says an Anthropic employee initially asked an internal research model to study a cryptographic question based on average-case Zero-k-Clique. Claude unexpectedly developed a new algorithm, first for the average-case setting and then for the worst case, during a session producing about 16 million output tokens with no human input. Anthropic shared the result with Alman and Vassilevska Williams, who reconstructed the argument, simplified it, improved constants and exponents, derived additional consequences and wrote the research paper. After the paper was complete, Anthropic used a research model to formalize major deterministic claims in Lean.
This event provides unusually explicit provenance for a frontier mathematical algorithm originating in a long autonomous model run and then surviving expert human reconstruction. The result does not merely improve a benchmark: it changes the conjectural landscape of fine-grained complexity and forces reconsideration of reductions and hardness assumptions built on 3SUM and APSP. The accompanying Lean artifact further makes a subset of the headline claims mechanically inspectable.
Significance rationale: This result is a Historical Milestone because it reports the first polynomial exponent improvements for 3SUM and APSP, two problems whose conjectured near-quadratic and near-cubic barriers structured fine-grained complexity for decades. The paper attributes the core algorithmic discovery to an Anthropic research model operating in a long session without human input, after which Josh Alman and Virginia Vassilevska Williams independently understood, simplified, strengthened and extended the method. Anthropic subsequently released a substantial Lean formalization of the principal deterministic claims.
—
—
—
The research paper publicly states the algorithmic results and gives an explicit account of the AI discovery workflow and subsequent human reconstruction.
Anthropic's public Lean project proves five headline deterministic claims, including the 3SUM and APSP word-RAM bounds, and documents Comparator/Nanoda checking procedures. The repository also explicitly lists paper claims that are not formalized in the same machine model. Chronicle has not located an independent external replay or specialist review sufficient for independently_verified status.
No corrections recorded.
