Kingy AI
Subscribe, 2.1M subscribersWork with Kingy

Breakthrough Tracker record

A formalized lower bound rules out 21-multiplication recursive integer 3×3 schemes

Rudich and Rousseau prove that recursive 3×3 block-matrix multiplication algorithms using integer constants require at least 22 multiplications. Within that restricted model, no 3×3 scheme can beat Strassen’s recursive exponent.

← Back to the filtered Breakthrough Tracker

Stable ID
cs-matrix-multiplication-recursive-3x3-lower-bound-2026
Revision
cs-matrix-multiplication-recursive-3x3-lower-bound-2026.v1
Field
Theoretical computer science · Algebraic complexity, tensor rank and formal verification
Evidence
Tier 1 · Peer reviewed: No
Record state
Provisional · Formalized restricted lower bound
Last checked

AI role

The authors report that Claude agents wrote search code and Lean proofs outside a roughly 1,000-line human audit surface; humans designed and reviewed that surface.

Record details

Problem or result
Minimum multiplication count for recursive 3×3 block algorithms with integer constants
Authors
Isaac Rudich and Louis-Martin Rousseau
Institutions
Polytechnique Montréal; Carnegie Mellon University
Result date
Deposits September 30; first-version preprint submitted October 1, 2026

Why it matters

The result closes the possibility that an integer-constant recursive 3×3 scheme with 21 multiplications can improve on Strassen and materially raises a long-stagnant restricted lower bound.

Limits

This reconciliation addition predates the prior cutoff but was absent from the dataset. It does not determine unrestricted 3×3 tensor rank, rule out non-integer constants or improve the general matrix-multiplication exponent; the author-supplied formalization has no independent semantic audit.

Sources

  1. Primary: Rudich and Rousseau, recursive 3×3 matrix-multiplication lower bound
  2. Formal proof: Lean proof deposit
  3. Primary archive: Paper deposit

Correction and revision history

  1. 2026-10-05 — Added after primary-source, scope, status, AI-role and limitation review.

Machine-readable: JSON v1 · CSV v1 · Schema v1

This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.