Page Content
to Navigation
There is no English translation for this web page.
Dr. Christian Ikenmeyer
- © Christian Ikenmeyer
University of Liverpool
Department of Computer Science
Ashton Building, Office 311
Ashton Street, Liverpool, L69 3BX
United Kingdom Persönliche Homepage
http://pcwww.liv.ac.uk/~iken/
Publikationen in der Arbeitsgruppe
| 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. |