3 papers
cs.DS2025
(Approximate) Matrix Multiplication via Convolutions
Yahel Uffenheimer, Omri Weinstein
We study the capability of the Fast Fourier Transform (FFT) to accelerate exact and approximate matrix multiplication without using Strassen-like divide-and-conquer. We present a s…
math.GR2025
Finite matrix multiplication algorithms from infinite groups
Jonah Blasiak, Henry Cohn, Joshua A. Grochow +2
The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group satisfying a s…
cs.DS2025
A note on Ordered Ruzsa-Szemerédi graphs
Kevin Pratt
A recent breakthrough of Behnezhad and Ghafari [FOCS 2024] and subsequent work of Assadi, Khanna, and Kiss [SODA 2025] gave algorithms for the fully dynamic -appro…