Logik in der Informatik Prof. Dr. Martin Grohe

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 AC⁰ circuits von Mark Braverman