TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation


Prof. Dr. Peter Bürgisser


Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Raum MA 317 (3. OG)
Institut für Mathematik


Beate Nießen
Raum MA 318
Tel.: +49 (0)30 314 - 25771


+49 (0)30 314 - 75902
+49 (0)30 314 - 25839

Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.


Geometric Complexity Theory and Tensor Rank
Zitatschlüssel BI-Geometric-Complexity-Theory-And-Tensor-Rank
Autor Peter Bürgisser and Christian Ikenmeyer
Buchtitel Proceedings 43rd Annual ACM Symposium on Theory of Computing 2011
Seiten 509-518
Jahr 2011
Zusammenfassung Abstract: Mulmuley and Sohoni (GCT1 in SICOMP 2001, GCT2 in 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(W_1)× GL(W_2)× GL(W_3)$ acting on the tensor product $W=W_1øtimes W_2øtimes W_3$ of complex finite dimensional vector spaces. Let $G_s = SL(W_1)× SL(W_2)× SL(W_3)$. A key idea from GCT2 is that the irreducible $G_s$-representations occurring in the coordinate ring of the $G$-orbit closure of a stable tensor $w\in W$ are exactly those having a nonzero invariant with respect to the stabilizer group of $w$. However, we prove that by considering $G_s$-representations, as suggested in GCT1-2, only trivial lower bounds on border rank can be shown. It is thus necessary to study $G$-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in GCT1-2. We prove a very modest lower bound on the border rank of matrix multiplication tensors using $G$-representations. This shows at least that the barrier for $G_s$-representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe