A few more words about AI

ADS2 · 12. 10. 2026 · Martin Koutecký

The only possible reaction is…

Holy shit!

Two cherry-picked results (and a bonus)

1. Matrix multiplication

Remember Strassen's algorithm from last semester?

• Naive: n³. Strassen 1969: n^{log₂ 7} ≈ n^2.807
• ω = the smallest exponent such that we can multiply n×n matrices in n^{ω + o(1)}
• We know 2 ≤ ω ≤ 2.807. Where exactly? Nobody knows.

OpenAI, An Upper Bound of 9/4 for the Matrix Multiplication Exponent (released 6 Oct 2026; written by an internal model). Over ℂ. Main theorem checked in Lean; not peer reviewed yet. Previous record ω < 2.371177: Dupont et al., Google DeepMind + Alman, Vassilevska Williams, Zhou (Aug 2026, with AlphaEvolve).

2. Integer multiplication

Remember Karatsuba's algorithm? n^{log₂ 3} ≈ n^1.585

• Schönhage–Strassen (1971): O(n log n log log n) — and they conjectured n log n is optimal
• Harvey–van der Hoeven (2019): O(n log n). Case closed?
• Oct 2026, OpenAI: O(n (log n)^1−κ) with κ = 2⁻¹⁸² ≈ 10⁻⁵⁵
  • multitape Turing machine, deterministic, exact — the same model as the conjecture
  • not peer reviewed, not formalized yet

OpenAI, Integer multiplication below n log n (released 6 Oct 2026; written by an internal model)

Now look at this: κ over three days

10⁻⁵⁵ → 10⁻³ in three days: hundreds of people + Codex / Claude improving OpenAI's construction (CrocSwap/integer-mult-bounds). Today: κ ≈ 1.5·10⁻³. All conditional on OpenAI's paper being correct. Screenshot: Beyond n log n dashboard by Aurel Prosz, posted by @dysmemic, 9 Oct.

Bonus: All-Pairs Shortest Paths

Remember Floyd–Warshall?

• Floyd–Warshall (1962): O(n³). For 60 years, nobody beat n³ by a polynomial factor
  (best: n³ / 2^{Ω(√log n)}, R. Williams 2014)
• "APSP hypothesis": no O(n^3−ε) algorithm exists. Many conditional lower bounds were built on it.
• Oct 2026: O(n^2.9995) — deterministic, directed, integer weights up to poly(n)
  (also real weights: O(n^2.998) expected; and 3SUM in O(n^1.9992))
• "Claude, an AI model developed by Anthropic, discovered the algorithm" — one session, 16M output tokens, no human input

Alman, Vassilevska Williams: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, arXiv:2610.06783 (5 Oct 2026). Main integer results checked in Lean.

So again, what's the point?

Look, regardless of the scenario:

Let's gooo!