direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

Explicit Lower Bounds via Geometric Complexity Theory
Zitatschlüssel BI-Explicit-Lower-Bounds-Via-Geometric-Complexity-Theory
Autor Peter Bürgisser and Christian Ikenmeyer
Buchtitel Proceedings 45th ACM Symposium on Theory of Computing
Seiten 141-150
Jahr 2013
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.