Aktuelles:
|
An dieser Stelle finden Sie im Laufe des Seminars aktuelle
Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
-
Die Vorbesprechung und Themenvergabe findet in der ersten
Semesterwoche am Dienstag, den 18.10.2005 um 15:15 Uhr in Raum 1.308,
Erwin Schrödinger-Zentrum, statt.
|
Einführung:
|
Viele Aspekte der elektronischen Datenverarbeitung können als eine Abfolge von Kommunikationsprozessen
betrachtet werden. Kommunikation ist immer dann nötig, wenn zwei oder mehr Computer, Komponenten,
Systeme oder Menschen gemeinsam eine Aufgabe lösen müssen, die keiner von ihnen allein bewältigen kann
– beispielsweise weil keiner alleine über die gesamten Daten oder Ressourcen verfügt. In vielen Fällen
ist die Kommunikation offensichtlich: Wenn wir z.B. Informationen im Internet suchen, werden unsere
Anfragen und die Antworten darauf über die Internetverbindung versendet. Es gibt aber auch Szenarien,
in denen die Kommunikation nur implizit stattfindet: Beim Lauf eines Computerprogramms etwa werden
Informationen zwischen den verschiedenen Komponenten des Rechners kommuniziert.
Das Gebiet der Kommunikationskomplexität beschäftigt sich mit der Frage, wie viel Kommunikation
zum Lösen bestimmter Aufgaben nötig ist.
Im Seminar werden Originalarbeiten und Buchabschnitte zum Thema behandelt.
Vorausgesetzt werden gute Kenntnisse der theoretischen Informatik.
|
Zeit und Raum:
|
Das Seminar findet immer dienstags, 15:00 - 16:30 Uhr, in Raum 1.308
(Erwin Schrödinger-Zentrum) statt.
Vorbesprechung und Themenvergabe sind in der ersten
Semesterwoche am Dienstag, den 18.10.2005 um 15:15 Uhr in Raum 1.308 (Erwin Schrödinger-Zentrum).
|
Literatur:
Einführende Literatur:
Literatur zu den einzelnen Vorträgen:
|
|
| [KN] |
E. Kushilevitz und N. Nisan.
Communication Complexity.
Cambridge University Press 1997. ISBN 0-521-56067-5.
(Lehrbuch, 189 Seiten)
|
| [NW] |
N. Nisan und A. Wigderson.
Rounds in Communication Complexity Revisited.
SIAM Journal on Computing, Vol. 22(1), Seiten 211-219, 1993.
(pdf-Datei auf
A. Wigdersons Homepage) |
| [K] |
E. Kushilevitz.
Privacy and Communication Complexity.
SIAM Journal on Discrete Mathematics, Vol. 5(2), Seiten 273-284, 1992.
(ps.Z-Datei auf
E. Kushilevitz' Homepage) |
| [BFJ] |
Z. Bar-Yossef, M. Fontoura und V. Josifovski.
Buffering in Query Evaluation over XML Streams.
Proceedings of PODS 2005: 24th ACM Sigact-Sigart Symposium on Principles of Database Systems,
Seiten 216-227, 2005.
(pdf-Datei auf
Z. Bar-Yossefs Homepage) |
| [GKS] |
Martin Grohe, Christoph Koch und Nicole Schweikardt.
Tight Lower Bounds for Query Processing on Streaming and
External Memory Data.
Proceedings of ICALP 2005: 32nd International Colloquium on Automata, Languages and Programming, Vol. 3580 of Lecture Notes in Computer Science, Springer-Verlag, Seiten 1076-1088.
(pdf-Datei der ausführlichen Version) |
| [MNSW] |
P. B. Miltersen, N. Nisan, S. Safra und A. Wigderson.
On Data Structures and Asymmetric Communication Complexity.
Journal of Computer and System Sciences, Vol. 57(1), Seiten 37-49, 1998.
(pdf-Datei auf
A. Wigdersons Homepage) |
| [DHS] |
M. Dietzfelbinger, J. Hromkovic und G. Schnitger.
A Comparison of two Lower-Bound Methods for
Communication Complexity.
Theoretical Computer Science, Vol. 168, Seiten 39-51, 1996.
(pdf-Datei auf
der www-Seite von Elsevier Science Direct) |
|
Mögliche Vortragsthemen:
|
-
Nichtdeterministische und deterministische Kommunikationskomplexität
([KN], Abschnitt 2.1-2.3)
-
Rechteckgröße und Rang; Einführung in die randomisierte Kommunikationskomplexität
([KN], Abschnitt 2.4-2.5 und 3.1-3.2)
-
Mehr zum Thema randomisierte Kommunikationskomplexität
([KN], 3.3-3.5)
-
Netzwerke, Kommunikation und VLSI – Kommunikationsmodelle mit variablen Partitionen
([KN], Kapitel 8 und Abschnitte 7.1-7.2)
-
Platz- und Zeitschranken – mehr zum Thema variable Partitionen
([KN], Kapitel 12 und Abschnitt 7.3)
-
Die Kommunikationskomplexität von Relationen
([KN], Kapitel 5)
-
Die Tiefe Boolescher Schaltkreise
([KN], Kapitel 10)
-
Kommunikationskomplexität für mehr als 2 Parteien
([KN], Abschnitte 6.1-6.4)
-
Mehr zur Tiefe Boolescher Schaltkreise — simultane Protokolle
([KN], Kapitel 11 und Abschnitt 6.5)
-
Die Anzahl von Kommunikations-Runden
([NW])
-
Geheimhaltung und Kommunikation
([K])
-
Der Speicherbedarf zur Auswertung von Anfragen an XML-Datenströme
([BFJ])
-
Untere Schranken für die Auswertung von Anfragen an Daten in externen Speichermedien
([GKS])
-
Entscheidungsbäume, Datenstrukturen und asymmetrische Kommunikation
([KN], Kapitel 9, Abschnitt 4.3 und Teile aus [MNSW])
-
"Fooling Set" vs "Rang": Vergleich zweier Methoden zum Nachweis unterer Schranken für
die Kommunikationskomplexität
([DHS])
|
Vorträge:
|
| Termin |
Thema |
Vortragende/r |
Zusammenfassung |
Ansprechpartner |
| 18.10.05 |
Themenvergabe |
|
|
|
| 25.10.05 |
Einführung in Kommunikationskomplexität
[KN], Kapitel 1 |
Nicole Schweikardt |
|
|
| 1.11.05 |
Einführung in Kommunikationskomplexität
(Fortsetzung vom 25.10.05) |
Nicole Schweikardt |
pdf-Datei |
|
| 8.11.05 |
Thema 1
[KN], Abschnitt 2.1-2.3 |
Thomas Kunze |
pdf-Datei |
André Hernich |
| 15.11.05 |
Thema 2
[KN], Abschnitt 2.4-2.5 und 3.1-3.2 |
Kornelius Kalnbach |
pdf-Datei
Ausarbeitung:
Teil 1,
Teil 2
|
André Hernich |
| 22.11.05 |
Thema 3
[KN], Abschnitt 3.3-3.5 |
André Hernich |
pdf-Datei |
|
| 29.11.05 |
Thema 4
[KN], Abschnitt 7.1-7.2 und Kapitel 8 |
André Hernich |
pdf-Datei |
|
| 6.12.05 |
frei
|
|
|
|
| 13.12.05 |
frei
|
|
|
|
| 20.12.05 |
Weihnachtsferien |
|
|
|
| 03.01.06 |
Thema 12
[BFJ]
(mit Schwerpunkt auf Kapitel 1-3)
|
Mathias Hasselmann |
|
Nicole Schweikardt |
| 10.01.06 |
frei
|
|
|
|
| 17.01.06 |
Thema 11
[K] |
Robert Goettsch |
|
Nicole Schweikardt |
| 24.01.06 |
Thema 5
[KN], Abschnitt 7.3 und Kapitel 12 |
Martin Borchardt |
|
André Hernich |
|
