Oberseminar Algebraische Komplexitätstheorie

Sommersemester 2008

Prof. Dr. Peter Bürgisser



Termin: Montag, 14:15 - 15:45 Uhr im E2.304 (normalerweise)

Beginn: Montag, den 14.04.2008

Wichtig: Wir bitten Interessenten, sich in die Mailingliste seminarca einzutragen.


Vorträge

14.04.2008 15:00 A3.232 Geglättete Analyse einer Konditionszahl der linearen Programmierung
und Dennis Amelunxen
28.04.2008 15:00 A3.232

In diesem Vortrag wird eine geglättete Analyse (smoothed analysis) der GCC-Konditionszahl der Linearen Programmierung vorgestellt. Eine geglättete Analyse kann als Ausgleich zwischen Grenzanalysen (worst case) und Durchschnittsanalysen (average case) interpretiert werden. Die einfache geometrische Bedeutung der GCC-Konditionszahl lässt eine geglättete Analyse mithilfe von Volumenabschätzungen von Mengen in Sphären zu.

Folien 1. Teil
Folien 2. Teil

29.05.2008 14:15 Hörsaal H6 Kolmogorov Complexity Theory over the Reals
Martin Ziegler (Joint work with Wouter M. Koolen from CWI Amsterdam...)

Kolmogorov Complexity constitutes an integral part of computability theory, information theory, and computational complexity theory --- in the discrete setting of bits and Turing machines. Over real numbers on the other hand, the BSS-machine (aka real-RAM) is well-established a major model of computation. This real realm has turned out to exhibit natural counterparts to many notions and results in classical complexity and recursion theory; although usually with considerably different proofs. We investigate similarities and differences between discrete and real Kolmogorov Complexity as introduced by Monatana and Pardo (1998).

02.06.2008 14:15 E2.304 The complexity of computing Kronecker coefficients
Christian Ikenmeyer

Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group S_n. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem KC of computing Kronecker coefficients is very difficult. More specifically, we prove that KC is #P-hard and contained in the complexity class Gap. Formally, this means that the existence of a polynomial time algorithm for KC is equivalent to the existence of a polynomial time algorithm for evaluating permanents.