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 |