TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

Explicit Lower Bounds via Geometric Complexity Theory
Citation key BI-Explicit-Lower-Bounds-Via-Geometric-Complexity-Theory
Author Peter Bürgisser and Christian Ikenmeyer
Title of Book Proceedings 45th ACM Symposium on Theory of Computing
Pages 141-150
Year 2013
Abstract We prove the lower bound $R(M_m) \ge \frac32 m^2 - 2$ on the border rank of $m × m$ matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's 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 $\mathrmSym^d \bigotimes^3(\mathbb C^n)^*$ and provide new insights into Kronecker coefficients.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe