On the asymptotic complexity of matrix multiplication
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Given one algorithm for multiplying matrices, there exists another, better, algorithm that cannot be realized by any single algorithm, and w, the exponent for matrix multiplication, is a limit point.
Abstract
The main results of this paper have the following flavor: given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that ω ≪ 2.495364.