The exponent-two conjecture for matrix multiplication
Let denote the exponent of matrix multiplication, equivalently the asymptotic exponent governing the border rank of the matrix multiplication tensors. Exponent-two conjecture.
This would establish the optimal possible asymptotic complexity for matrix multiplication. The source presents it as a special case of a broader conjecture, but no resolution evidence is supplied here.
References
Primary source
Giorgio Ottaviani and Philipp Reichenbach, “Tensor Rank and Complexity”, arXiv:2004.01492 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 3
RemarkAI-assistedClaimed by OpenAI.See full solution
Claimed by OpenAI.
Claims that for every epsilon > 0, two n-by-n complex matrices can be multiplied in O_epsilon(n^(9/4+epsilon)) arithmetic operations, so the complex exponent is at most 9/4; this is progress toward exponent two.
Repository: https://github.com/openai/math
- OpenAI-107-01-An-Upper-Bound-of-9-4-for-the-Matrix-Multiplication-Exponent.pdfOpen
RemarkAI-assistedClaimed by OpenAI.See full solution
Claimed by OpenAI.
Claims omega < 2.258, alpha > 0.465, and omega(1,0.709,1) < 2.092 over characteristic-zero fields, with the stated square and rectangular bounds outside a finite exceptional set of positive characteristics; this is progress toward exponent two.
Repository: https://github.com/openai/math
- OpenAI-107-02-Complex-Matrix-Multiplication-Below-2-258-and-Rectangular-Bounds.pdfOpen
RemarkAI-assistedClaimed by OpenAI.See full solution
Claimed by OpenAI.
Claims omega_F < 2.371054886006746 for every fixed field F, including every positive characteristic, in the arithmetic-operation model; this is progress toward exponent two.
Repository: https://github.com/openai/math
- OpenAI-107-03-Staggered-extraction-for-exact-matrix-multiplication-over-every-field.pdfOpen