Kommunikationskomplexität

Voraussetzungen:
Grundkenntnisse der Komplexitätstheorie z.B. aus Informatik III

Beschreibung:
Gegeben ist eine Funktion f. Alice kennt x und Bob kennt y. Wieviele Bits müssen die beiden austauschen, um f(x,y) zu bestimmen? Dieses Problem taucht in verschiedensten Berechnungsproblemen auf: Wenn mehrere Computer, Komponenten, Systeme, oder auch Personen (allgemein ``Parteien) gemeinsam eine Aufgabe lösen sollen, die keine der Parteien allein lösen kann, da sie nicht über alle Daten verfügt, dann müssen die Komponenten miteinander kommunizieren. Bei entfernten Parteien wird ``explizit kommuniziert (z.B. über Telefonleitungen). In anderen Fällen erfolgt die Kommunikation ``implizit (Kommunikation zwischen verschieden Teilen des Computers, zwischen verschiedenen Teilen eines Mikroprozessors usw.). Manchmal findet gar keine reale Kommunikation statt, dennoch ist es nützlich, sich eine Berechnung abstrakt als Kommunikationsprozeß vorzustellen. Man reduziert so das unübersichtliche Berechnungsproblem auf eine überschaubare kombinatorische Aufgabenstellung in der Hoffnung, Rückschlüsse auf das Ausgangsproblem ziehen zu können. In der Vorlesung sollen u.a. Anwendungen auf binäre Entscheidungsgraphen, untere Schranken für Schaltkreistiefe, Area-Time-Tradeoff für VLSI-Schaltkreise, Energieaufwand bei VLSI-Schaltkreisen, Multiparty-Kommunikation, und Beziehungen zur Kryptographie behandelt werden.

Literatur:

1. E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge University Press, 1997.
2. J. Hromkovic. Communication Complexity and Parallel Computing. Springer, 1997.