Explicit lower bounds via geometric complexity theory

DOI10.1145/2488608.2488627MaRDI QIDQ5495784zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser, Christian Ikenmeyer

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.8368

zbMATH Keywords

determinantgeometric complexity theoryKronecker coefficientsmatrix multiplicationpermanenttensor rank

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Abstract: We prove the lower bound R(M_m) geq 3/2 m^2 - 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of the geometric complexity theory (GCT) program. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is the new combinatorial concept of obstruction designs, which encode highest weight vectors in Sym^dotimes^3(C^n)^* and provide new insights into Kronecker coefficients.

Recommendations

• Geometric complexity theory and tensor rank
• New lower bounds for the border rank of matrix multiplication
• Unifying known lower bounds via geometric complexity theory
• New lower bounds for matrix multiplication and
• On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry

Cited in

(21)

• On vanishing of Kronecker coefficients
• Equations for GL invariant families of polynomials
• Bounds on Kronecker coefficients via contingency tables
• Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case
• Unifying known lower bounds via geometric complexity theory
• The Saxl conjecture and the dominance order
• Geometric aspects of iterated matrix multiplication
• scientific article; zbMATH DE number 3883608 (Why is no real title available?)
• On geometric complexity theory: multiplicity obstructions are stronger than occurrence obstructions
• Tensor rank: matching polynomials and Schur rings
• No occurrence obstructions in geometric complexity theory
• On geometric complexity theory: multiplicity obstructions are stronger than occurrence obstructions
• Fundamental invariants of orbit closures
• Geometric complexity theory and tensor rank
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• Some unimodal sequences of Kronecker coefficients
• Tensor rank and complexity
• Geometric complexity theory for product-plus-power
• Two classes of minimal generic fundamental invariants for tensors
• 16,051 formulas for Ottaviani's invariant of cubic threefolds
• Two-sided complexity bounds for Löbell manifolds

This page was built for publication: Explicit lower bounds via geometric complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495784)