New fastest deterministic 3SUM algorithm hits n^1.9961, matching randomized bound
basedjensen · x · 2026-10-10
A new record for the 3SUM problem: the fastest known deterministic algorithm now runs in n^1.9961 — a 4.5× saving below n² with zero randomness, matching the best randomized bound. The advance builds on the paper "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs" by Josh Alman and Virginia Vassilevska Williams, which uses triangles in sparse lopsided graphs to yield both subquadratic 3SUM and subcubic APSP results — a major breakthrough in fine-grained complexity.
More from Research
- Retrieval-centric deep learning: replacing weight matrices with vector databases — RobertTLange · 2026-10-10
- SJTU's UVTA teaches robot dexterous manipulation from 1,000 human tactile demos per task — siyuanhuang95 · 2026-10-10
- 20-minute explainer breaks down how Tesla trains FSD: 8 cameras, 36fps, 2B signals to 2 outputs — PTrubey · 2026-10-10
- 21 researchers release white paper on Visual General Intelligence as a path to AGI — HirokatuKataoka · 2026-10-10
- Epoch AI: Over half of arXiv math papers in 3 subfields now acknowledge AI use — burny_tech · 2026-10-10
- Researcher faults standard Transformer diagrams for hiding self-attention as a black box — PlisSergey · 2026-10-10