Geometry and the complexity of matrix multiplication

Abstract

We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i.) to show how open questions in algebraic complexity theory are naturally posed as questions in geometry and representation theory, (ii.) to motivate researchers to work on these questions, and (iii.) to point out relations with more general problems in geometry. The key geometric objects for our study are the secant varieties of Segre varieties. We explain how these varieties are also useful for algebraic statistics, the study of phylogenetic invariants, and quantum computing.

arXiv comment34 pages, 4 figures

References in corpus (5)

• The Schmidt Measure as a Tool for Quantifying Multi-Particle Entanglement
• Group-theoretic algorithms for matrix multiplication
• Phylogenetic ideals and varieties for the general Markov model
• On the ideals and singularities of secant varieties of Segre varieties
• Generalizations of Strassen's equations for secant varieties of Segre varieties