RUB » LMI » Lehre » Seminar über Komplexitätstheorie SS 2010

Seminar über Komplexitätstheorie SS 2010

LVR-Nr: 150 526
Veranstaltung: Seminar über Komplexitätstheorie
Di 16.15 - 17.45, NA 1/64
Dozent: Hans U. Simon

Kommentar

Das Seminar behandelt ausgewählte Themen der Komplexitätstheorie mit einem besonderen Fokus auf Kommunikationskomplexität. Zur Bestimmung der Kommunikationskomplexität einer Funktion in zwei Parametern wird untersucht, wieviel Bits an Kommunikation zwischen zwei "Spielern" nötig ist, wobei jeder der Spieler Kenntnis über genau einen der beiden Eingabeparameter besitzt. Die Kommunkationskomplexität ist ein wichtiges Werkzeug zum Nachweis der inhärenten Härte eines Problemes. Zum Beispiel spielt sie eine Rolle beim "Zeit-Flächen-Tradeoff" bei hochintegrierten Schaltkreisen (VLSI-Circuits). Im BSc-Studienabschnitt kann das Seminar zusammen mit der Vorlesung "Theoretische Informatik" und der Bachelorarbeit (die eine Ausarbeitung des Seminarvortrages ist) für Modul 10 verwendet werden.

Die Anmeldung erfolgte bereits auf der ersten Seminarsitzung am 13. April. Weitere Interessentinnen und Interessenten sind aber willkommen.

Vorraussetzungen

Grundkenntnisse in Theoretischer Informatik wie sie etwa in der Vorlesung Theoretische Informatik. vermittelt werden: diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden relativ rasch im Selbststudium herstellbar.

Literatur

1. Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997.
2. Troy Lee and Adi Shraibman, Lower Bounds in Communication Complexity, in: Foundations and Trends in Theoretical Computer Science, Vol. 3, No. 4, 263-399, 2007.

Das Buch von Kushilevitz und Nisan kann in der UB ausgeliehen werden. In der Mathe-Bibliothek steht ein Präsenzexemplar.
Der Forschungsbericht von Lee und Shraibman ist ab sofort in der Mathe-Bibliothek verfügbar und kann ausgeliehen werden. S.~auch Updates der Autoren.

Zeitplan (wird später noch erweitert)

20.04.2010 Kapitel 1 aus Kushilevitz/Nisan: Basics Dozent
04.05.2010 Kapitel 2 aus Kushilevitz/Nisan: More on Covers (Teil 1) Julia Bührig-Neupert und Christian Schauf
11.05.2010 Kapitel 2 aus Kushilevitz/Nisan: More on Covers (Teil 2) Julia Bührig-Neupert und Christian Schauf
18.05.2010 Kapitel 3 aus Kushilevitz/Nisan: Randomization (Teil 1) Katharina Kohls und Heiko Mattern
01.06.2010 Kapitel 3 aus Kushilevitz/Nisan: Randomization (Teil 2) Katharina Kohls und Heiko Mattern
08.06.2010 Kapitel 2.3 aus Lee/Shraibman: Norm-Based Methods Philipp Wagner
15.06.2010 Kapitel 3 aus Lee/Shraibman: Nondeterministic Communication Complexity Pia Radine
22.06.2010 Kapitel 4 aus Lee/Shraibman: Randomized Communication Complexity (Teil 1) Rinat Davletshyn und Johannes Hollad
29.06.2010 Kapitel 4 aus Lee/Shraibman: Randomized Communication Complexity (Teil 2) Rinat Davletshyn und Johannes Hollad
06.07.2010 Kapitel 6 aus Lee/Shraibman: The Role of Duality in Proving Lower Bounds Sebastian Gischus
13.07.2010 Kapitel 7 aus Lee/Shraibman: Choosing a Witness Elena Böhme
20.07.2010 Kapitel 5 aus Lee/Shraibman: Quantum Communication Complexity Florian Giesen