A lower bound for langle 3,2,m rangle matrix multiplication

Askar Tsyganov; Uliana Parkina; Sergey Samsonov; Maxim Rakhuba

In the authors' words

We prove that, over any field, the bilinear complexity of multiplying a $3 \times 2$ matrix by a $2 \times m$ matrix is strictly greater than $24 m /5$ . In particular, every exact bilinear algorithm for multiplying a $3 \times 2$ matrix by a $2 \times 5$ matrix requires at least $25$ multiplications. Together with the Hopcroft-Kerr upper bound, this proves that the $⟨ 3, 2, 5 ⟩$ matrix multiplication tensor has rank exactly $25$ . The proof has been formally verified in Lean 4, with the formalization available at https://github.com/fallnlove/mm325_proof.

Main resultThe abstract does not state a limitation.

A lower bound for ⟨3,2,m⟩ matrix multiplication

In the authors' words

More on Algorithms & complexity that day

Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

Dynamic Contention Resolution Schemes

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

TokaGLINT: A Scalable GPU-Tailored Implicit Solver for Full 3D Tokamak Electromagnetic Simulations

A lower bound for $⟨ 3, 2, m ⟩$ matrix multiplication