New algorithm cuts (min,+) matrix multiplication exponent to 2.9964, beating Anthropic's breakthrough
thegautamkamath · x · 2026-10-17
A new arXiv note by Barna Saha and Christopher Ye gives a deterministic algorithm computing the (min, +)-matrix product of two N×N integer matrices in Õ(N^2.9964), improving on the O(N^2.9995) from Anthropic's recent breakthrough (Alman and Vassilevska Williams, 2026). It builds on the 2016 phased-approximation framework and uses the thin matrix product theorem from that breakthrough to construct the previously missing sparse certificate, yielding a modular truly-subcubic APSP algorithm. Gautam Kamath adds that some researchers privately find such simplification papers imperfect, but applauds the direction.
More from Research
- SYNTH team's jspace analysis: Baguettotron layer topology radically differs from Gemma-270m — voooooogel · 2026-10-17
- Tangermeme published in Nature Methods: an 'everything-but-the-model' toolkit for genomic deep learning — anshulkundaje · 2026-10-17
- Context Inertia: when LLM agents latch onto a wrong hypothesis and won't let go — rseroter · 2026-10-17
- Microsoft's MAI-Base-2 blog source code leaks intermediate checkpoint validation losses — YouJiacheng · 2026-10-17
- Axolotl v0.21.0 ships 501B MoE QLoRA fine-tuning on a single 8xH200 node — ethayarajh · 2026-10-17
- AI-generated math proofs spark debate: solutions too complex for experts to verify — frugal-tech-worker · 2026-10-17