Zeit und Ort: nach Vereinbarung
WICHTIG: der im Vorlesungsverzeichnis angegebene Termin Do 0800-1000 gilt nicht.
Jeder Teilnehmer soll alleine, oder in Gruppen von maximal 3 Studenten, 1-2 publizierte Arbeiten aus dem Bereich
Kommunikationskomplexität bearbeiten und vortragen. Um dies zu erleichtern, wird eine Einführung in dieses Gebiet
und die Informationstheorie gegeben. Als letzter Vortrag wird Ran Raz, Parallel Repetition Theorem vorgestellt
und bewiesen.
Inhalt
Dieses Seminar soll einen Einblick in die Kommunikationskomplexität, einem etablierten Teilgebiet der
Komplexitätstheorie, geben. Wie der Name schon sagt, wird hier in verschiedenen Modellen verteilter
Systeme die Resource "Kommunikation" untersucht. Wollen nämlich zwei oder mehr Parteien in einem
verteilten System ein nichttriviales Problem lösen, für welches sie jeweils nur einen Teil der
Eingabe besitzen, so müssen die Parteien miteinander kommunizieren. Die Kommunikationkomplexität
ist dann die minimale Anzahl von kommunizierten Bits, die zur Lösung des Problems notwendig sind.
Die Kommunikationskomplexität ist sehr facettenreich mit Anwendungen in Bereichen wie Interactive Proofs,
Propositional Proof Complexity, Theorie der Booleschen Funktionen (Schaltkreiskomplexität und VLSI),
Kryptographie (Information Privacy), etc.
Mögliche Themen:
Direkte-Summen-und-Produkt-Theoreme: Eine grundlegende Fragestellung in jedem Berechnungsmodell ist, wie der
Resourcenbedarf, um mehrere Probleme gemeinsam zu lösen, sich zur Summe der Einzelkomplexitäten
verhält.
Ein wichtiges Problem im Hinblick auf untere Schranken für Boolesche Funktionen ist das sog. Pointer Jumping Problem.
Hier wird untersucht, inwieweit sich die Komplexität des Problems bei Einschränkung der Runden erhöht.
Rundenhierarchien: Man kann die Existenz von Funktionen (wie Pointer Jumping) zeigen, die in k Runden leicht zu lösen
sind, wo man aber bei Beschränkung auf k-1 Runden exponentiell mehr kommunizieren muss.
Anwendungen in der Propositional Proof Complexity: Untere Schranken in der Kommunikationskomplexität
im NOF Modell führen zu superpolynomiellen unteren Schranken für die Beweiskomplexität in Beweissystemen.
Anwendungen in der Theorie der Booleschen Funktionen: Zu jeder Booleschen Funktion kann man eine Relation R_f
definieren mit D(R_f) = Schaltkreistiefe von f. Beschränkt man sich auf monotone Schaltkreise, so ergeben sich
superlogarithmische untere Schranken für die Schaltkreistiefen konkreter Funktionen.
Untere Schranken in der Kommunikationskomplexität: Die Kommunikationskomplexität für ein Problem genau
zu bestimmen, ist ein schwieriges Problem. Es sind deshalb eine ganze Reihe von Methoden entwickelt worden, diese
zumindest annäherungsweise zu bestimmen, unter anderen: Fourier-, Corruption-, Diskrepanz-Methode, ...
Logarithmische-Rang-Vermutung: Eine weitere untere-Schranke-Methode für die deterministische Kommunikationskomplexität
ist, den Logarithmus des Ranges der Kommunikationsmatrix des Problems zu berechnen. Es stellt sich die (offene) Frage,
wie gut diese Methode ist. Zum einen kann man einen polynomiellen gap zeigen, zum anderen kann dieses Problem auf ein
Problem in der algebraischen Geometrie reduziert werden.
Kontakt
Bei Interesse wenden Sie sich bitte zur Themenvergabe an
Henning Wunderlich .
Henning Wunderlich, 19.03.2007
