Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich.
mehr Informationen...
ger: 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_{\lambda,\mu}^\nu ergeben einen Polynomialzeitalgorithmus zum Entscheiden von c_{\lambda,\mu}^\nu >= t mit Laufzeit polynomiell in n und quadratisch in t, wobei n die Anzahl der Teile von \nu ist. Für t = 1, also zum Testen der Positivität von c_{\lambda,\mu}^\nu, bekommen wir sogar eine Laufzeit von n^3 log \nu_1.Darüber hinaus führen unsere Einsichten zu einem Beweis einer Vermutung von King, Tollu und Toumazet (CRM Proc. Lecture Notes, 34, Symmetry in Physics: 99-112), welche besagt, dass aus c_{\lambda,\mu}^\nu = 2 immer c_{M\lambda,M\mu}^{M\nu}= M + 1 für alle M \in \N folgt.
eng: 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_{\lambda,\mu}^\nu yields a polynomial time algorithm for deciding c_{\lambda,\mu}^\nu >= t in time polynomial in n and quadratic in t, where n denotes the number of parts of \nu. For t = 1, i.e., for checking positivity of c_{\lambda,\mu}^\nu, we even obtain a running time of n^3 log \nu_1.Moreover, our insights lead to a proof of a conjecture by King, Tollu, and Toumazet (CRM Proc. Lecture Notes, 34, Symmetry in Physics: 99-112), stating that c_{\lambda,\mu}^\nu = 2 implies c_{M\lambda,M\mu}^{M\nu} = M + 1 for all M \in \N.