| 17.10.05: | Wiederholung GTI (Kapitel 1-6 im Buch) | |
| 19.10.05: | Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit (7.2), Definition Approximationsalgorithmen (8.1), Anfang Approximationsalgorithmen (8.2) | |
| 24.10.05: | Approximationsalgorithmen (8.2) zu Ende, Lückentechnik (8.3) | |
| 26.10.05: | Approximationserhaltende Reduktionen (8.4), vollständige Approximationsprobleme (8.5). | |
| 31.10.05: | NP versus co-NP (10.2), Orakelklassen (10.3), Anfang polynomielle Hierarchie (10.4) | |
| 2.11.05: | Satz von Wrathall (10.4 zu Ende), Satz von Lautemann (Anfang 10.5) | |
| 7.11.05: | Beziehung BPP und NP, relativierte Komplexitätstheorie (10.5 zu Ende) | |
| 9.11.05: | Exkurse "Hierarchiesätze" und "Universelles Hashing". Definition interaktive Beweissysteme (Anfang Kap.11 bis 11.2 einschließlich). | |
| 14.11.05: | Graphnichtisomorphie in IP(2), BPNP = AM (Anfang von 11.3). | |
| 16.11.05: | Wiederholung AM-Protokolle, Vorbereitungen für Beweis, das Graphnichtisormorphie in AM. | |
| 21.11.05: | Graphnichtisormorphie in AM, Anfang ZK-Protokolle (Anfang 11.4). | |
| 23.11.05: | ZK-Protokolle i.W. zu Ende (11.4). | |
| 28.11.05: | Definitionen für PCP-Theorem, Anfang des Beweises für NP = PCP(n^3,1) (12.1 und Anfang 12.2) | |
| 30.11.05: | Beweis für NP = PCP(n^3,1) bis Anfang Konsistenztester (12.2) | |
| 5.12.05: | Beweis für NP = PCP(n^3,1) fertig (12.2), Gap-Variante von MAX-3-SAT NP-schwer | |
| 7.12.05: | Beweis von MAX-3-SAT MAX-APX-vollständig bis auf Rechnung (Anfang 12.4) | |
| 12.12.05: | MIN-APX-Problem auf MAX-APX-Problem per PTAS-Reduktion (Ende 12.4), Anfang Platzkomplexität (Kap.13) | |
| 14.12.05: | Satz von Savitch, randomisierte Platzkomplexität (absolutes Halten vs. fast sicheres Halten, RL = NL), log. Reduktionen und Graph-s-t-Connectivity-Probleme | |
| 2.1.06: | Einführung nichtuniforme Komplexität (14.1-14.4): Simulationen SKs <-> TMs, Einführung Branchingprogramme und Simulationen BPs <-> TMs, Kommunikationskomplexität: Einführung des Modells (15.1). | |
| 4.1.06: | Rechteckmaßmethode (einfach, Vollversion, Unterscheidungsmengen, Anwendung auf GT, EQ, DISJ und IP -- Anfang 15.2). | |
| 9.1.06: | Rangmethode, Protokolle mit variabler Partition und untere Schranke für Multiplikation, Anfang nichtdeterministische Protokolle (15.3). | |
| 11.1.06: | Nichtdeterminismus fertig (15.3), Definitionen rand. Protokolle und Fingerprinting (Anfang 15.4). | |
| 16.1.06: | Öffentlicher Zufall und Satz von Newman, Yaos Minimax-Prinzip. | |
| 18.1.06: | Diskrepanzmethode und untere Schranke für IP, Kommunikationskomplexität von Relationen, Anwendungen für VLSI und 1-Band-TMs (Kap.15 Ende). | |
| 23.1.06: | Komplexität boolescher Fktn.: Bausteineliminierung, Nechiporuk, Vorbereitungen für Karchmer-Wigderson (Anfang Kap. 16). | |
| 25.1.06: | Karchmer-Wigderson-Methode und Anwendung für Set Cover, AC^k-Schaltkreise, obere Schranke für PARITY. | |
| 30.1.06: | PARITY nicht in AC^0 mit Austauschlemma, Überblick ACC^k-Klassen, Anfang Thresholdschaltkreise (16.5). | |
| 1.2.06: | IP nicht in TC^{0,2}, Größe von Branchingprogrammen (Abschnitt 16.6). | |
| 6.2.06: | Erzeugung von Zufallszahlen, Disperser und Zufallsbiteinsparung bei Probability-Amplification (17.1-17.3) | |
| 8.2.06: | Expanderbasierte Disperser (Ende 17.3), Verbesserung schlechter Zufallsquellen (17.4), Derandomisierung zeit- und platzbeschränkter Klassen im Schnelldurchlauf (17.5+17.6). |