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 |