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_
Titelaufnahme
- TitelGeometric complexity theory, tensor rank, and Littlewood-Richardson coefficients
- Autor
- Prüfer
- Erschienen
- HochschulschriftPaderborn, Univ., Diss., 2012
- AnmerkungTag der Verteidigung: 18.10.2012
- SpracheEnglisch
- DokumenttypDissertation
- URN
- Social MediaShare
- Nachweis
- IIIF
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_
- Das PDF-Dokument wurde 547 mal heruntergeladen.