2011 · 56 citations · 20 references
Natural SciencesComputer ScienceMathematicsAlgebraGeometryRepresentation TheoryAbstract AlgebraAlgebraic GeometryGroup TheoryInvariant TheoryLinear AlgebraMatrix ComputationFinite-dimensional Vector SpacesGeometric Invariant TheoryGroup Representation TheoryIrreducible RepresentationsLower BoundsMatrix MultiplicationOrbit Closures
Mulmuley and Sohoni [GCT1, SICOMP 2001; GCT2, SICOMP 2008] proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group G =GL(W1) x GL(W2) x GL(W3) acting on the tensor product W=W1 ⊗ W2 ⊗ W3 of complex finite dimensional vector spaces. Let Gs =SL(W1) x SL(W2) x SL(W3). A key idea from [GCT2] is that the irreducible Gs-representations occurring in the coordinate ring of the G-orbit closure of a stable tensor w ∈ W are exactly those having a nonzero invariant with respect to the stabilizer group of w.
20
J. H. van Lint · 2020 · 4.5K citations
Matrix multiplication via arithmetic progressions
Don Coppersmith, S. Winograd · Journal of Symbolic Computation · 1990 · 2.3K citations
Instability in Invariant Theory
George R. Kempf · Annals of Mathematics · 1978 · 420 citations
Rank and optimal computation of generic tensors
Volker Strassen · Linear Algebra and its Applications · 1983 · 199 citations