SE Kommunikationskomplexität
Dozent: Prof. Dr. Christoph Berkholz
Das Bachelorseminar "Kommunikationskomplexität" findet digital statt. Informationen und aktuelle Mitteilungen werden im Moodle-Kurs der Lehrveranstaltung unter
https://moodle.hu-berlin.de/course/view.php?id=97939
bereitgestellt. Alle Teilnehmer*innen müssen sich dort anmelden, der Einschreibeschlüssel für den Moodle-Kurs wird an die in Agnes zugelassenen Studierenden verschickt. Alternativ kann der Einschreibeschlüssel auch per E-Mail an den Dozenten erfragt werden.
Inhalt
Wie viel Kommunikation ist nötig, um eine Funktion zu berechnen, wenn die Eingabebits auf zwei oder mehrere Parteien aufgeteilt sind? Diese Frage steht im Zentrum der Kommunikationskomplexität, einem Teilgebiet der theoretischen Informatik. Mit der Beantwortung dieser Frage für konkrete Funktionen liefert die Kommunikationskomplexität ein elegantes und mächtiges mathematisches Werkzeug zum Beweisen von unteren Schranken in verschiedenen Berechnungsmodellen. In diesem Seminar sollen Methoden und Ergebnisse der Kommunikationskomplexität erarbeitet und präsentiert werden.
Die Vortragsthemen orientieren sich an den folgenden beiden Büchern (PDF-Versionen sind aus dem HU-Netz verfügbar):
- Eyal Kushilevitz und Noam Nisan. Communication complexity. Cambridge University Press, 1997.
- Anup Rao und Amir Yehudayoff. Communication Complexity: And Applications. Cambridge Core. Cambridge University Press, Januar 2020.
Zeitplan
- Mittwoch, 28. Oktober 2020. Ende der zentralen Einschreibefrist in Agnes, anschließend Anmeldung im Moodle-Kurs.
- Freitag, 6. November, 11:15 - 12:45. Gemeinsame Vorbesprechung via ZOOM (verpflichtend für alle Teilnehmer*innen, die ZOOM-Zugangsdaten werden über Moodle bekannt gegeben).
- Dezember 2020. Individuelle Vorbesprechungstermine.
- An einem oder mehreren Freitagen im Januar 2021. Durchführung des Blockseminars via ZOOM.
- Bis 31. März 2021. Abgabe der Seminarausarbeitungen.