Oberseminar Algebraische Komplexitätstheorie

Wintersemester 2008/2009

Prof. Dr. Peter Bürgisser



Termin: Montag, 14:15 - 15:45 Uhr im D1.320 (normalerweise)

Beginn: Montag, den 10.11.2008

Vorträge

10.11.2008 14:15 D1.320 A combinatorial polynomial-time algorithm for deciding the positivity of Littlewood-Richardson coefficients
und Christian Ikenmeyer
24.11.2008 14:15 D1.320

Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group GL_n(C). The coefficients have a wide variety of interpretations in combinatorics, representation theory, geometry, and in the theory of symmetric functions. It is known that the problem of computing Littlewood-Richardson coefficients is #P-complete. Quite surprisingly, as first pointed out by Mulmuley and Sohoni, it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining Knutson and Tao's proof of the Saturation Conjecture (1999) with the fact that linear optimization is solvable in polynomial time. We present an explicit combinatorial polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and uses ideas from the theory of optimizing flows in networks.