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

Askar Tsyganov; Uliana Parkina; Sergey Samsonov; Maxim Rakhuba

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

Askar Tsyganov, Uliana Parkina, Sergey Samsonov, Maxim Rakhuba

PreprintCódigo disponible

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF Código

Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

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

En palabras de los autores

Más de Algoritmos y complejidad ese día

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