In der theoretischen Informatik gehört die Analyse der Komplexität von Algorithmen und Problemstellungen zu einem der zentralsten Forschungsbereichen. Klassischerweise wird unter "Komplexität" dabei die "Zeitkomplexität" verstanden; man interessiert sich also grob gesagt dafür, wie viele Rechenschritte ein Algorithmus zum Bearbeiten einer Eingabe eines Problems benötigt, und ob es schnellere Algorithmen geben kann. Die zugrundeliegende Annahme ist dabei meist, dass beliebig viel schneller Speicher verfügbar ist, und ein einzelner Prozessor die Rechenschritte abarbeitet.
Betrachtet man heutige Ausführungsumgebungen genauer, so treffen diese Annahmen in der Regel nicht zu: Große Datenmengen liegen verteilt auf verschiedenen Systemen (oder verteilt auf mehrere getrennte Komponenten eines Rechners) und müssen für die Berechnung einer Ausgabe zusammengeführt werden. Im Zentrum der Communication Complexity steht nun die Analyse der Kommunikation, die zwischen den verteilten Systemen erfolgt bzw. erfolgen muss, bis die Ausgabe feststeht. Die Erkenntnisse aus diesen Analysen können insbesondere Anwendung finden beim Entwurf von Schaltkreisen, dem Entwickeln effizienter Datenstrukturen sowie der Gestaltung von Netzwerken und Protokollen für verteilte Systeme.
Fokus der Lehrveranstaltung ist eine Einführung in das mathematische Modell der Communication Complexity, Entwurfstechniken für Kommunikationsprotokolle sowie Analysetechniken für untere und obere Schranken an den Umfang der benötigten Kommunikation zwischen den beteiligten Parteien. Als Anwendungsfelder werden insbesondere einfache Streaming-Algorithmen, Chip-Design sowie Datenstrukturen betrachtet. Zudem wird das Modell auch aus dem Blickwinkel der Data Privacy beleuchtet.
