Hauptseminar im Wintersemester 2004/05

Computational Limitations for Small Depth Circuits

Kontaktpersonen:

Daniel Mölle (moelle@informatik.rwth-aachen.de)
Stefan Richter (richter@informatik.rwth-aachen.de)
Peter Rossmanith (rossmani@informatik.rwth-aachen.de)

Einordnung

Theoretische Informatik

Ort und Zeit

Jeweils donnerstags von 15:00 bis 16:30 Uhr im Raum 6329 (Erweiterungsbau E2).

Inhalt

Johan Håstad schrieb 1986 seine Doktorarbeit "Computational Limitations for Small Depth Circuits" und erhielt dafür den Preis der ACM für die beste Dissertation des Jahres. In dieser Arbeit wird bewiesen, daß bestimmte Funktionen durch Schaltkreise mit beschränkter Tiefe und polynomieller Größe nicht berechnet werden können. Er erfand hierfür sehr elegante mathematische Methoden, um untere Schranken zu beweisen. Inhalt des Seminars ist genau diese Arbeit.

Voraussetzungen

Vordiplom. Man sollte Spaß an Mathematik haben.

Hinweise

Das Seminar ist nichttraditionell! Wir arbeiten gemeinsam das Buch "Computational Limitations for Small Depth Circuits" durch. Die TeilnehmerInnen halten jede Woche einen Einführungsvortrag zum nächsten Abschnitt. Danach wird dieser gemeinsam bearbeitet und diskutiert. Abschließend erfolgt eine Zusammenfassung der Ergebnisse durch zufällig gewählte Studierende im Rahmen eines kurzen spontanen Vortrags.

Neu: Das im PS-File fehlende Inhaltsverzeichnis und die dort ebenfalls fehlenden Abbildungen stehen jetzt zum Download zur Verfügung.


Themenverteilung

erfolgt online.