---
type: "post"
id: "a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd"
slug: "a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd"
title: "A new preprint presents a simpler 3SUM algorithm and deterministic results for real inputs"
description: "Summary A new arXiv preprint by Timothy M. Chan Reina Itakura Zhiyuan Ma and Yuancheng Yu presents a randomized truly subquadratic algorithm for integer 3SUM that avoids matrix multiplication. It also reports results for odd-k SUM and deterministic algorithms for"
retrieval_nugget: "A new arXiv preprint by Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu presents a randomized, truly subquadratic algorithm for integer 3SUM that avoids matrix multiplication. It also reports results for odd-k SUM and deterministic algorithms for real-valued 3SUM and APSP, extending a fast-moving theoretical line with a different and, the authors say, simpler route."
published_at: "2026-11-16"
updated_at: "2026-11-16"
record_date: "2026-11-16"
date_kind: "published_at"
topics: ["anthropic"]
entities: ["Timothy M. Chan","Reina Itakura","Zhiyuan Ma","Yuancheng Yu","Anthropic","arXiv"]
related_patterns: []
novelty_label: "new_fact"
what_changed: "A new preprint offers a matrix-multiplication-free subquadratic 3SUM algorithm, refutes the k-SUM hypothesis for odd k, and gives deterministic real-input 3SUM/APSP algorithms."
prior_refs: ["https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347/","https://newruntime.com/posts/majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a/"]
source_url: "https://arxiv.org/abs/2610.42012"
source_urls: ["https://arxiv.org/abs/2610.42012"]
schema_version: "newruntime-agent-readable-v0.2"
stable_id: "post:a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd"
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/a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd/","markdown":"https://newruntime.com/posts/a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd.md","json":"https://newruntime.com/posts/a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd.json"}
markdown_url: "https://newruntime.com/posts/a-new-preprint-presents-a-simpler-3sum-algorithm-b12ddd.md"
---

# A new preprint presents a simpler 3SUM algorithm and deterministic results for real inputs

## Retrieval answer

A new arXiv preprint by Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu presents a randomized, truly subquadratic algorithm for integer 3SUM that avoids matrix multiplication. It also reports results for odd-k SUM and deterministic algorithms for real-valued 3SUM and APSP, extending a fast-moving theoretical line with a different and, the authors say, simpler route.

## Summary
A new arXiv preprint by Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu presents a randomized, truly subquadratic algorithm for integer 3SUM that avoids matrix multiplication. It also reports results for odd-k SUM and deterministic algorithms for real-valued 3SUM and APSP, extending a fast-moving theoretical line with a different and, the authors say, simpler route.

## What happened
The paper, submitted to arXiv on October 30, 2026, is titled “3SUM Made Simpler (Without Matrix Multiplication), k-SUM Hypothesis Refuted for Odd k, and Real 3SUM/APSP Derandomized.” Its authors are Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu. The arXiv listing categorizes it under Data Structures and Algorithms and identifies the submission as version 1. Its abstract presents three results; it is a preprint, not a report of a released implementation.

First, the authors give a different randomized algorithm for 3SUM with integer inputs. 3SUM asks whether a set of numbers contains three whose sum is zero. The abstract characterizes the new algorithm as truly subquadratic: its running time grows asymptotically more slowly than the familiar quadratic scale in the number of input values. The method avoids matrix multiplication entirely. Instead, it modifies known dynamic-programming algorithms for subset convolution and the zeta transform, relying on subtraction tricks based on inclusion-exclusion. The authors say the approach does not require fast Fourier transform and that the complete solution is about five pages long. The abstract does not state a particular exponent for this algorithm.

Second, following a similar approach, the paper reports a randomized algorithm for k-SUM on integer inputs when k is an odd constant. Its stated running time is O(n^{⌈k/2⌉−ε_k}) for some constant ε_k greater than zero. The authors say this refutes the k-SUM Hypothesis for all odd k. The abstract does not quantify ε_k for individual values of k or provide implementation timings.

Third, the authors address real-valued inputs and determinism. They say existing reductions from 3SUM and APSP to selected-entry rectangular matrix multiplication were randomized for real-valued inputs. Their new deterministic reductions yield a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP. The announcement does not give specific exponents for those two results, nor does it describe a software package, benchmark suite, access conditions, or price. The contribution described is a theoretical algorithmic result.

## What the archive adds
New Runtime's earlier coverage traces a related sequence of 3SUM and APSP results. On October 28, 2026, [an earlier note covered a simplified proof of 3SUM and APSP improvements](https://newruntime.com/posts/lovett-and-karingula-post-a-simplified-proof-of-a20347/). On October 31, [New Runtime covered a preprint reporting stronger exponents for 3SUM and APSP](https://newruntime.com/posts/majdoddin-preprint-improves-the-claude-found-3sum-apsp-e9401a/). This is a new fact on that known story: the authors propose an alternative integer 3SUM method without matrix multiplication and add deterministic results for real inputs.

## Trend signal
This does not yet fit a pattern New Runtime tracks. The paper concerns advances in asymptotic algorithm design, but the patterns tracked here do not specifically cover faster classical combinatorial algorithms. Its connection to prior 3SUM/APSP work is clear; that alone does not make it evidence for a broader pattern about production AI systems or agent workflows.

## Why now
The preprint arrives shortly after the related 3SUM/APSP results described in New Runtime's October 28 and October 31, 2026 coverage. Its timing matters in that research sequence: it offers a distinct algorithmic route and extends the discussion to deterministic reductions for real-valued inputs. The arXiv record gives October 30, 2026 as the submission date; the source does not identify a conference decision or publication schedule.

## Connections to other events
The authors explicitly frame their work against algorithms for 3SUM and APSP recently found by Anthropic, as reported by Alman and Vassilevska Williams (2026). Those earlier algorithms relied on a subroutine for rectangular matrix multiplication with selected output entries, itself obtained by modifying known techniques. Chan and coauthors take a different route for integer 3SUM, then separately provide deterministic reductions for real-valued 3SUM and APSP. New Runtime's October 31 coverage also discussed a preprint improving bounds for the Claude-found 3SUM/APSP algorithm; the present work adds an alternative approach rather than simply reporting another exponent improvement.

## Why it matters
For algorithm designers, the paper separates a fast 3SUM result from the selected-entry matrix multiplication machinery used in the preceding line of work. Avoiding matrix multiplication may make the proof easier to inspect and teach, especially given the authors' claim that the core solution is about five pages. The result also broadens the theoretical picture: for odd constant k, the stated bound challenges a hypothesis that had served as a benchmark for expected k-SUM complexity.

The distinction between integer and real-valued inputs, and between randomized and deterministic algorithms, is consequential. A theoretical bound does not automatically translate into a faster service: practical performance depends on constants, data representation, input sizes, and implementation details that the abstract does not report. Still, teams working on algorithms, computational geometry, or exact optimization may want to track the full paper. It provides a new design direction and claims deterministic guarantees in settings where the cited reductions were randomized.

## Limits and uncertainty
The arXiv abstract reports asymptotic guarantees but does not specify the exponent for the integer 3SUM algorithm, the constants ε_k for particular odd k, or concrete exponents for the real-valued results. It gives no benchmark measurements, implementation, code, or evidence about performance at practical input sizes. The claims have not been independently assessed here, and an arXiv submission is not, by itself, confirmation of peer review or acceptance. The full proof and its assumptions determine how broadly each result applies; readers should inspect those before treating the abstract's summary as an implementation specification.

## Skill to build now
If your work involves exact 3SUM-style algorithms, compare the paper's model and assumptions with your own problem before considering an implementation. Start by writing down whether inputs are integers or real-valued, whether randomization is acceptable, and which complexity guarantee matters. Then read the proof alongside your current algorithm and identify the specific subroutine it replaces. This is a concrete way to assess whether a theoretical result changes a design choice without assuming that an asymptotic improvement will win on production-sized inputs.

## Reader takeaway
The important change is not a benchmark win but a new theoretical route: the authors claim a truly subquadratic integer 3SUM algorithm built without matrix multiplication, alongside odd-k and deterministic real-input results. It strengthens the algorithmic picture, while practical payoff remains an open question until the bounds, constants, and implementations are examined in detail.

## Open question
What concrete exponents and practical crossover points emerge when the full algorithms are implemented and compared with existing 3SUM and APSP methods?

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`.

- topic hub: [Anthropic](https://newruntime.com/topics/anthropic.md): Explore the anthropic topic hub.
- collection: [Field Notes](https://newruntime.com/posts.json): Open the latest editorial analysis.
- collection: [Sources](https://newruntime.com/sources/): See the original sources this archive cites.
- whole graph: [discovery graph](https://newruntime.com/discovery-graph.json) (typed nodes and edges) and [site index](https://newruntime.com/site-index.md)
