Algorithms for graph problems, string comparison, arithmetic, and exact search.
10 records · Includes focused interests · How we rate progress
Alman 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-22The 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 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-06Algorithms for graph problems, string comparison, arithmetic, and exact search. We separate proved complexity bounds from empirical performance, and retain the computation model and input restrictions.
This topic groups related mathematical questions across publishers. Each focused problem carries its own baseline and each contribution retains its original source. Results are compared only when their assumptions, optimization target, and computation model agree.
Background review: 2026-10-11. Selected sources:
Publication dates and editorial changes.
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.
