Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
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…
cs.CC2025
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
Josh Alman, Jingxun Liang
For an matrix , its rank- rigidity, denoted , is the minimum number of entries of that one must change to make its rank become at most .…
cs.CC2024
Improving the Leading Constant of Matrix Multiplication
Josh Alman, Hantao Yu
Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in t…