4 papers
The edge of the asymptotic spectrum of tensors
Josh Alman, Baitian Li, Kevin Pratt
Strassen founded the theory of the asymptotic spectrum of tensors to study the complexity of matrix multiplication. A central challenge in this theory is to explicitly construct ne…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…
Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Josh Alman, Baitian Li
We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''re…
Faster Convolutions: Yates and Strassen Revisited
Cornelius Brand, Radu Curticapean, Baitian Li +1
Given two vectors over a finite domain and a function , the convolution problem asks to compute the vector whose…