Go to page
 

Bibliographic Metadata

Title
Geometric complexity theory, tensor rank, and Littlewood-Richardson coefficients
AuthorIkenmeyer, Christian
ExaminerBlömer, Johannes ; Bürgisser, Peter ; Landsberg, Joseph M.
Published2012
Institutional NotePaderborn, Univ., Diss., 2012
Annotation
Tag der Verteidigung: 18.10.2012
LanguageEnglish
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-10472 
Files
Geometric complexity theory, tensor rank, and Littlewood-Richardson coefficients [2.1 mb]
Links
Reference
Classification
Abstract (German)

Diese Arbeit führt gründlich in die Geometrische Komplexitätstheorie ein, ein Ansatz, um untere Berechnungskomplexitätsschranken mittels Methoden aus der algebraischen Geometrie und Darstellungstheorie zu finden. Danach konzentrieren wir uns auf die relevanten darstellungstheoretischen Multiplizitäten, und zwar auf Plethysmenkoeffizienten, Kronecker-Koeffizienten und Littlewood-Richardson-Koeffizienten. Diese Multiplizitäten haben eine Beschreibung als Dimensionen von Höchstgewichtsvektorräumen, für welche konkrete Basen nur im Littlewood-Richardson-Fall bekannt sind.Durch explizite Konstruktion von Höchstgewichtsvektoren können wir zeigen, dass der Grenzrang der m x m Matrixmultiplikation mindestens 3 m^2 - 2 ist, und der Grenzrang der 2 x 2 Matrixmultiplikation genau sieben ist. Dies liefert einen neuen Beweis für ein Ergebnis von Landsberg (J. Amer. Math. Soc., 19:447-459, 2005).Desweiteren erhalten wir Nichtverschwindungsresultate für rechteckige Kronecker-Koeffizienten und wir beweisen eine Vermutung von Weintraub (J. Algebra, 129 (1): 103-114, 1990) uber das Nicht-Verschwinden von Plethysmen-koeffizienten von geraden Partitionen.Unsere eingehenden Untersuchungen zu Littlewood-Richardson-Koeffizienten c_

Abstract (English)

We provide a thorough introduction to Geometric Complexity Theory, an approach towards computational complexity lower bounds via methods from algebraic geometry and representation theory. Then we focus on the relevant representation theoretic multiplicities, namely plethysm coefficients, Kronecker coefficients, and Littlewood-Richardson coefficients. These multiplicities can be described as dimensions of highest weight vector spaces for which explicit bases are known only in the Littlewood-Richardson case.By explicit construction of highest weight vectors we can show that the border rank of m x m matrix multiplication is a least 3 m^2 - 2 and the border rank of 2 x 2 matrix multiplication is exactly seven. The latter gives a new proof of a result by Landsberg (J. Amer. Math. Soc., 19:447-459, 2005).Moreover, we obtain new nonvanishing results for rectangular Kronecker coefficients and we prove a conjecture by Weintraub (J. Algebra, 129 (1): 103-114, 1990) about the nonvanishing of plethysm coefficients of even partitions.Our in-depth study of Littlewood-Richardson coefficients c_