Algorithms for graphs, strings, arithmetic, and matrix multiplication, together with computational complexity.
19 records · Includes focused interests · How we rate progress
The manuscript reports one deterministic algorithm computing the exact complex discrete Fourier transform at every length n in O(n(log n)^(1−10^−13)) operations, including scalar preparation, scheduling and indexing, in its specified arithmetic model.
Read original source Pinned manuscript, Theorem 1.1 and Corollary 1.2github.com
Original report: 2026-10-06The AlphaEvolve report gives a rank-48 decomposition of the 4×4 matrix-multiplication tensor over the complex numbers, yielding a bilinear algorithm using 48 scalar multiplications.
Read original source AlphaEvolve technical report, §3.1arxiv.org
Original report: 2025-05-14DeepMind reports AI-discovered assembly sorting routines translated to C++ and incorporated in LLVM libc++. Its tests report up to 70% improvement for length-five inputs and about 1.7% for inputs exceeding 250,000 elements.
Original report: 2023-06-07OpenAI reports a deterministic polynomial-time reduction from 3SAT to fixed-alphabet Unique Games with completeness at least 1−ε and soundness at most δ for each fixed ε,δ in (0,1/2).
Read original source Original manuscript: claim, hypotheses, and contextgithub.com
Original report: 2026-10-06OpenAI reports a uniform deterministic logarithmic-space simulation of polynomial-time randomized logarithmic-space decision procedures with bounded error, yielding L=RL=BPL.
Read original source Original manuscript: claim, hypotheses, and contextgithub.com
Original report: 2026-10-06OpenAI reports uniform deterministic complete factorization of a densely represented polynomial over a binary-specified prime field in bit complexity polynomial in (degree+1) log p, including irreducible factors and multiplicities.
Read original source Original manuscript: claim, hypotheses, and contextgithub.com
Original report: 2026-10-06Alman and Vassilevska Williams report deterministic O(n^1.9992) 3SUM on polynomial-size integers and O(n^2.9995) APSP with polynomially bounded integer weights in the word-RAM model.
Read original source Alman–Vassilevska Williams: algorithms and methodologyarxiv.org
Original report: 2026-10-05Coester, Koutsoupias and Zbysiński report that the work function algorithm is k-competitive on every metric space.
Original report: 2026-09-14The artifact reports (3,4,5,20,22,36) schedulable but (3,4,5,20,22,32) unschedulable, refuting the proposed six-task kernel cap.
Read original source Original researchgithub.com
Original report: 2026-09-30Becker, Greger and Peters report that every approval-based multiwinner election has a core committee and that one can be found in polynomial time.
Original report: 2026-09-10The AFP development records a seven-vertex instance with fractional cost 58 but unsplittable cost at least 60, even allowing additive congestion 15.
Read original source Original researchisa-afp.org
Original report: 2026-07-22Dupont and collaborators report ω<2.371177 by improving the combination-loss optimization and refining it with AlphaEvolve.
Original report: 2026-08-17The manuscript reports a deterministic quasipolynomial algorithm for the nonnegative-value vertices of finite turn-based stochastic mean-payoff games.
Read original source Original manuscript · family 104github.com
Original report: 2026-10-06The manuscript reports that the complex matrix-multiplication exponent is at most 9/4.
Read original source Original manuscript · family 107github.com
Original report: 2026-10-06The manuscript reports deterministic multiplication in O(n (log n)^(1−κ)) time with κ = 2^−182 on a fixed finite-tape Turing machine.
Read original source Original manuscript · family 109github.com
Original report: 2026-10-06The manuscript reports a randomized algorithm taking (n+m)^(1+o(1)) time and returning a maximum matching with probability at least 2/3.
Read original source Original manuscript · family 120github.com
Original report: 2026-10-06The manuscript reports a randomized (1+ε)-approximation in N^(1+o(1)) worst-case expected time for each fixed rational ε in (0,1).
Read original source Original manuscript · family 121github.com
Original report: 2026-10-06The manuscript reports a randomized classical Subset Sum algorithm in O(2^(0.49n)) time for polynomial-bit inputs.
Read original source Original manuscript · family 138github.com
Original report: 2026-10-06The authors report an algorithm multiplying 4×4 matrices over the two-element field using 47 scalar multiplications, compared with 49 from two levels of Strassen’s algorithm.
Original report: 2022-10-05Algorithms for graphs, strings, arithmetic, and matrix multiplication, together with computational complexity.
Related focused topics and problems retain their own statements and baselines. A contribution may belong to more than one field; it is counted once within each topic.
Background review: 2026-10-11. Selected sources:
Publication dates and editorial changes.
OpenAI reports: a power saving for exact discrete Fourier transforms
OpenAI reports: Deterministic factorization over prime fields
Claude-assisted truly subquadratic 3SUM and subcubic shortest paths
AI-assisted core existence in approval-based committee elections
AI-assisted counterexample to cost-preserving unsplittable flow
OpenAI reports: Almost-linear approximation of edit distance
Anthropic: Lean formalizations of 3SUM and shortest-path bounds
OpenAI reports: Almost-linear approximation of edit distance
Allow optional Google Analytics to help improve AIProofWatch? Privacy details.
