Commutative coherent configurations suffice for matrix multiplication exponent two
Commutative coherent configurations suffice for matrix multiplication exponent two
A coherent configuration is a finite set equipped with a partition of its ordered pairs into basis relations; it is commutative when its adjacency algebra is commutative. A coherent configuration realizes the matrix multiplication tensor when the associated tensor realization has matrix dimensions , and its rank is the number of basis relations.
Commutative coherent configuration conjecture. There exist commutative coherent configurations realizing and of rank .
Such configurations would provide a route to proving that the matrix multiplication exponent satisfies . The paper gives commutative coherent configurations yielding nontrivial upper bounds on , but the asserted rank- family is not established here.
Sources & referencesView supporting material
Primary source
Henry Cohn and Christopher Umans, “Fast matrix multiplication using coherent configurations”, arXiv:1207.6528 (2012).
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 0
Sign in to submit a solution.
No solutions have been posted yet.