Aktuelles
Am 8. Mai wird kein Seminar stattfinden.
Einführung
In diesem Semester werden wir uns eingehend mit der Komplexität boolescher Schaltkreise beschäftigen.
Das Seminar setzt sehr gute und zumindest in einem Bereich auch
tiefergehende Kenntnisse der theoretischen Informatik voraus.
Literatur
Sanjeev Arora, Boaz Barak: Complexity Theory -- A Modern Approach. Chapter 14: Circuit Lower Bounds (draft).
http://www.cs.princeton.edu/theory/index.php/Compbook/Draft#circuitlb
Zeit und Raum
Freitags 9-11 im
Schrödinger Zentrum (Rudower Chaussee 26),
Raum 1'308.
Vorträge
-
17.4.2009 Vorbesprechung und Themenvergabe
-
24.4.2009 Kord Eickmeyer, über: Håstads Switching Lemma und untere Schranken für Parity und Majority.
-
Mi. 29.4.2009, 13ct Kord Eickmeyer, Fortsetzung vom 24.4.2009.
-
1.5.2009 Feiertag
-
8.5.2009 kein Seminar
-
15.5.2009 Christoph Berkholz, über: Untere Schranken für monotone Schaltkreise.
-
5.6.2009 Mark Weyer, über: ACC -- Schaltkreise mit (mod p)-Zählgattern.
-
12.6.2009 Martin Grohe, über: Poly-logarithmic
independence fools AC0 circuits von Mark Braverman