Veranstalter:		Martin Sauerhoff
Termin:		Montag		12:15-13:45 Uhr		HS 112 / GB IV
		Mittwoch		08:30-10:00 Uhr		HS 1, OH 14 (Informatik-Neubau)
Beginn:		17. Oktober 2005

Die Vorlesung ist beendet.

Diese Vorlesung hat im Wintersemester den Schwerpunkt Komplexitätstheorie und im Sommersemester den Schwerpunkt Effiziente Algorithmen. Ein Besuch beider Vorlesungen ist sinnvoll und für eine Spezialisierung in diesen Bereichen sehr nützlich.

Hinweise zu Prüfungen

Vorlesungsankündigung
Was wurde wann gemacht?
Informationen zu den Übungen
Begleitmaterial (Vorlesungsfolien, Übungsblätter, Testfragen)
Zusätzliche Literatur und nützliche Links

Begleitmaterial

Vorlesungsfolien: Revised Edition

Inhaltliche Änderungen in der Revised Edition

Vorlesungsfolien: Online-Version aus der Vorlesung

Übungsblätter

Zusätzliche Literatur und nützliche Links

Kapitel 8:

A compendium of NP optimization problems.
(Editoren: P. Crescenzi und V. Kann.)

Kapitel 10:

• J. L. Balcázar, J. Díaz, J. Gabarró, "Structural Complexity I", Springer 1995.
  Kap.7: Beweis von Satz 10.2.1 aus der Vorlesung.
• Completeness in the polynomial-time hierarchy -- a compendium
  (Marcus Schaefer und Christopher Umans, 2005).
• K. R. Reischuk, "Komplexitätstheorie", Teubner 1990.
  (Dies ist die alte Version des in der Literaturliste am Anfang der Vorlesung genannten Buches.)
  Abschnitt 6.4.4: Relativierte Ergebnisse zu P versus NP.
• "The 'P =? NP'-Poll" von Bill Gasarch, 2002.
  (Vielleicht nicht direkt ein "nützlicher" Link im strengen Sinne, aber unterhaltsam auf jeden Fall.)

Kapitel 11:

• T.H.Cormen, C.H.Leiserson, R.L.Rivest, C.Stein, "Introduction to Algorithms", 2nd Edition, MIT Press, 2001.
  Kap.11.3.3: Weitere Details zu universellem Hashing.
• O. Goldreich, "Zero-knowledge twenty years after its invention", 2004.
  Tutorial mit mehr Details (teilweise technisch anspruchsvoll) zum Thema von Abschnitt 11.4.
• O. Goldreich, "Foundations of Cryptography (Fragments of a Book)", 1995.
  Fragmentarische Vorversionen von einigen Kapiteln des gleichnamigen Buches (2 Bände, Cambridge University Press, 2004).

Kapitel 12:

• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, "Complexity and Approximation", Springer-Verlag, 1999.
• E.W.Mayr, H.J.Prömel, A.Steger (Hrsg.), "Lectures on Proof Verification and Approximation Algorithms", LNCS 1367, Springer-Verlag, 1998.
• S. Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems", PhD Thesis, UC Berkeley, 1994.
  Kostenlose Version des vollständigen Beweises des PCP-Theorems (im alten Stil).
• I.Dinur, "The PCP theorem by gap amplification", Technischer Bericht ECCC, 2005.
  Neue, nur 22-seitige Version (April 2005) des vollständigen Beweises des PCP-Theorems.
  Der Beweisverifizierer aus dem Beweis von Satz 12.2.2 in der Vorlesung ist auch als Teil dieses neuen Beweises hilfreich.

Kapitel 15:

• J. Hromkovič, "Communication Complexity and Parallel Computing", Springer-Verlag, 1997.
• E. Kushilevitz, N. Nisan: "Communication Complexity", Cambridge University Press, 1997.
• Mehr Informationen zum Thema Spieltheorie (und Beweis des Minimax-Theorems):
  Thomas Hofmeister & Ingo Wegener, Skript "Operations Research", WS 2000/01.

Kapitel 16:

• S. Jukna, "Extremal Combinatorics", Springer-Verlag, 2001.
  ("Extremal" bezieht sich hier auf die Eigenschaften der kombinatorischen Objekte, die untersucht werden -- nicht auf den Schwierigkeitsgrad!)
• I. Wegener, "Branching Programs and Binary Decision Diagrams", SIAM, 2000.
• I. Wegener, "Complexity of Boolean Functions", Teubner, 1987.
• Vollständiger Beweis von Lemma 16.6.11 der Vorlesung.
• Skovbjerg Frandsen, Bro Miltersen, "Reviewing Bounds on the Circuit Size of the Hardest Functions", Technischer Bericht ECCC, 2005.
  Asymptotisch exakte Abschätzung der Worstcase-Formelgröße, untere Schranke mit "shannonschem Abzählargument" wie in der Vorlesung.
• Untere Schranken für die BP-Größe von Funktionen mit vielen Ausgabebits.
  (Ein geplanter Abschnitt von Kapitel 16, der aus Zeitgründen nicht behandelt wurde.)

P. Bro Miltersen, "Derandomizing Complexity Classes", 1999.

Informationen zu den Übungen:

Das erste Übungsblatt wird in der Vorlesung am 19.10. verteilt. Alle weiteren Übungsblätter werden NICHT in der Vorlesung verteilt, sondern sind jeweils mittwochs (Blatt 2 am 26.10.) ab 10.00 Uhr hier verfügbar und liegen im GB IV auf dem Flur im 2.Stock zwischen Raum 325 und Raum 326 aus (Lehrstuhl 2).

Jedes Übungsblatt enthält in der Regel 4 Aufgaben zu jeweils 5 Punkten. Eine Abgabe darf von maximal 2 Personen gemeinsam erstellt werden. Werden Lösungen von mehreren Gruppen gemeinsam erarbeitet, so muss jede Gruppe ihre Lösung eigenständig formulieren und aufschreiben. Bitte bei jeder Abgabe Name, Matrikelnummer und Übungsgruppennummer angeben! Einen Übungsschein erhält, wer

1. insgesamt 50 % der auf den Blättern erreichbaren Punkte erreicht und
2. regelmäßig an den Übungsgruppen teilnimmt und dort die eigenen Lösungen vorstellt.

Übungsgruppen: