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 InformatikOrt 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.