Rafael Pass gives constructive proof of matrix multiplication exponent ω ≤ 9/4
srush_nlp · x · 2026-11-03
Rafael Pass released a new paper, Matrix Multiplication from Polynomial Packings, providing a self-contained constructive proof of the matrix multiplication exponent bound ω ≤ 9/4, following OpenAI's recent breakthrough.
- OpenAI's original result established the bound in the exact scalar arithmetic model over the complex numbers using non-constructive arguments in Strassen's asymptotic spectral framework. Pass explicitly constructs a Strassen-style multiplication identity and obtains the bound via ordinary block recursion.
- For any γ > 0, the resulting algorithm multiplies two n×n integer matrices with O(n^(9/4+γ)) integer arithmetic operations.
- Independent contribution: a framework of polynomial packings — reducing many polynomial multiplications to fewer ones with linear operations. Pass isolates and generalizes an OpenAI construction and shows packings can be composed to amplify their compression rate, yielding Strassen-like identities.
More from AGI Musings
- Agents attacking at scale will finally make the best cybersecurity products win — _shreya_s · 2026-11-03
- M&A partner runs 20+ deals on AI, but 'build, baby, build' isn't a strategy — jkubicki · 2026-11-03
- Dev argues agents make experimentation so cheap you should be 10x more scientific — zack_overflow · 2026-11-03
- Investor breaks down the AI trade: models improve exponentially, automated economy coming fast — abhiadesai · 2026-11-03
- Claude persona dominance sparks concern: we need models that aren't 'Claudes' — mimi10v3 · 2026-11-03
- ML PhDs Ask: With AI Research Jobs So Competitive, Was the Doctorate Worth It? — Hope999991 · 2026-11-03