RUB » LMI » Lehre » Seminar über "Komplexität 0,1-wertiger Funktionen" SS 2020

Seminar über Komplexität 0,1-wertiger Funktionen SS 2020

LVR-Nr: 150 545
Veranstaltung: Seminar über Komplexität 0,1-wertiger Funktionen
Mo 16.15 - 17.45, IA 1/109 (Beginn voraussichtlich am 20.04.)
Dozent: Hans U. Simon

News

  • Die Vortragstermine sind jetzt unten in der Tabelle eingetragen. Alle Seminarsitzungen finden online statt (als Zoom-Meeting).

Kommentar

Gegenstand des Seminars ist die Komplexität Boolescher Funktionen. Wir werden uns insbesondere mit der Kommunikationskomplexität einer Booleschen Funktion f(x,y) beschäftigen: - Bitstrings x und y sind auf zwei Parteien A und B verteilt. - Wieviele Bits muessen zwischen A und B ausgetauscht werden, damit das Ausgabebit f(x,y) korrekt bestimmt werden kann? Kommunikationskomplexität hat viele Anwendungen und dient oft als Werkzeug zum Nachweis der inhärenten Härte eines Berechnungsproblems. Die Bestimmung der Kommunikationskomplexität erfolgt mit Werkzeugen aus der Diskreten Mathematik und der Linearen Algebra.

Voraussetzungen

Teilnehmerinnen und Teilnehmer am Seminar sollten über solide Kenntnisse in linearer Algebra und diskreter Mathematik verfügen.

Literatur

Das Seminar orientiert sich an den Lehrbüchern ``Boolean Function Complexity'' von Stasys Jukna und ``Communication Complexity'' von Eyal Kushilevitz und Noam Nisan. Diese Bücher werden im Folgenden ``Buch 1'' und ``Buch 2'' genannt.

Buch 1 steht in der Mathe-Bibliothek als Präsenzexemplar. Buch 2 ist mit folgender url campusweit freigeschaltet und in Kürze im Katalog RUB zu finden: https://doi.org/10.1017/CBO9780511574948
(Buch 2 ist zudem auch in der Mathe-Bibliothek vorrätig.)

Zeitplan

18. Mai Kap. 3, S. 81-92, Buch 1 Games on Relations Jan Röse
25. Mai Kap. 4.1-4.3, S. 93-104, Buch 1 Games on 0,1-Matrices Luisa Christin Kasa und Lena-Sophie Wedel
08. Juni Kap. 4.4-4.6, S. 104-114, Buch 1 Games on 0,1-Matrices Dominik Reichert und Christopher Saal
15. Juni Kap. 4.7-4.10, S. 114-124, Buch 1 Games on 0,1-Matrices Hao-Xiang Jimi Chan und Ziyuan Yuan
22. Juni Kap. 4.11-4.12, S.124-129, Buch 1 Games on 0,1-Matrices Tim Strunkheide
29. Juni Kap. 5.1-5.4, S. 135-143, Buch 1 Multi-Party Games Elena Hoster
06. Juli Kapitel 10, Buch 2 Bounded Circuit Depth Kathrin Krupa
13. Juli Kapitel 12, Buch 2 Time and Space Lisa-Marie Lehmann