Kommunikationskomplexität
Wintersemester 2007/2008
|
| Veranstalter: | | Martin Sauerhoff | |
|
| Umfang der Veranstaltung: | | 2 SWS Vorlesung | |
|
| Termin: | | Mittwoch | | 10:15-11:45 Uhr | | OH 14, 304
|
| Beginn: | | 17. Oktober 2007 | |
|
Die Vorlesung ist beendet.
[Inhalt] [Begleitmaterial] [Literatur und nützliche Links]
Alice in Aachen und Bob in Böblingen verfügen jeweils über eine lokale Kopie
einer 1 Terabyte umfassenden Datenbank. Wie können die beiden mit möglichst
geringem Verbrauch an Netzbandbreite feststellen, ob ihre Datenbanken
konsistent sind? Tatsächlich kann man relativ einfach zeigen, dass ein
optimales deterministisches Protokoll zum Informationsaustausch durch
die triviale Vorgehensweise gegeben ist, bei der einer der beiden
Parteien dem jeweils anderen seinen kompletten Datenbankinhalt
übermittelt. Wenn wir allerdings randomisierte Protokolle zulassen,
kann das Problem durch Übertragung von nur logarithmisch vielen
Bits in der Datenbankgröße gelöst werden, im konkreten Beispiel
mit ungefähr 140 Bytes (statt 1 TB) bei einer
Fehlerwahrscheinlichkeit von 1 %.
Wir werden in der Vorlesung das formale Modell der
Kommunikationsprotokolle behandeln, mit dem sich Probleme
wie das obige genau beschreiben und analysieren lassen.
Ein wesentliches Ziel in der Kommunikationskomplexitätstheorie
ist es, für elementare Probleme untere Schranken für den
Kommunikationsaufwand nachzuweisen, der notwendig ist, um
diese in verteilter Form zu lösen. Entsprechende Beweistechniken
werden wir uns in der Vorlesung erarbeiten. Diese Ergebnisse haben
vielfältige Anwendungsmöglichkeiten beim Nachweis von unteren
Schranken für anwendungsnahe Berechnungsmodelle, wie z.B. für die
OBDD-Größe, Tradeoffs zwischen Fläche und Zeit von VLSI-Schaltkreisen,
Rechenzeit von 1-Band-Turingmaschinen, Tiefe von monotonen
Schaltkreisen usw.
Grundlage der Vorlesung ist das Buch von Kushilevitz
und Nisan (siehe Begleitmaterial) und Originalarbeiten.
Nach einem Einführungsteil werden wir folgende fortgeschrittene Themen
behandeln:
- Protokolle mit beschränkter Rundenanzahl;
- Mehrspielerprotokolle;
- elementare Informationstheorie und Anwendungen für den Nachweis von unteren Schranken;
- Anwendungen für Branchingprogramme und Zeit-Speicherplatz-Tradeoffs;
- Quantenkommunikationskomplexität.
Der Einführungsteil wird sich zum Teil mit dem entsprechenden
Abschnitt aus der Vorlesung "Komplexitätstheorie" in diesem Semester
überschneiden, da wir kein Wissen von dort voraussetzen.
Die Vorlesung wird sich an folgendem Buch orientieren:
E. Kushilevitz, N. Nisan. "Communication Complexity". Cambridge University Press, 2006.
Bei amazon.de.
Ergänzende Notizen (Version: 28.1.08).
Ein weiteres, ergänzendes Buch über Kommunikationskomplexität:
J. Hromkovič. "Communication Complexity and Parallel Computing". Springer,
1998.
Bei amazon.de.
Ein Standardwerk für den informationstheoretischen Teil der Vorlesung:
T. M. Cover, J. A. Thomas. "Elements of Information Theory". Wiley, 2006.
Bei amazon.de.
M. Sauerhoff