Zur Merkliste hinzufügen


63989-01 - Seminar: Advanced Computational Complexity Theory 4 KP

Semester Frühjahrsemester 2022
Angebotsmuster unregelmässig
Dozierende Malte Helmert (malte.helmert@unibas.ch, BeurteilerIn)
Gabriele Röger (gabriele.roeger@unibas.ch)
Inhalt Every week, we study one of the chapters of Arora and Barak's textbook on computational complexity (see "Bibliography").

Warning: while the textbook used for the seminar is self-contained, it advances at a rapid pace aimed to educate researchers on complexity theory. It is likely to be too challenging for participants that have not studied computational complexity theory before. Participants should feel comfortable with concepts of computational complexity theory such as the theory of NP-completeness, polynomial reductions, and Turing machines.
Lernziele Participants develop an in-depth understanding of advanced modern computational complexity theory through self-study, discussion, solving exercises and reviewing exercises.
Literatur Sanjeev Arora and Boaz Barak: Computational Complexity – A Modern Approach. Cambridge University Press, 2009.
Bemerkungen The focus of the course as a whole is on individual self-study, with the main benefits obtained from the reading that happens between seminar sessions. The focus of the seminar sessions is on resolving questions and answers related to the chapter of the week in a non-supervised peer discussion. No prepared presentations are planned.


Teilnahmebedingungen There are no formal admission requirements (but see "Content").
Anmeldung zur Lehrveranstaltung Registration via MOnA/Services. Non-student participants and participants from other universities that cannot register in this way are welcome -- please contact the organizers for access details.
Unterrichtssprache Englisch
Einsatz digitaler Medien kein spezifischer Einsatz
HörerInnen willkommen


Intervall wöchentlich
Datum 24.02.2022 – 02.06.2022
Zeit Donnerstag, 16.15-18.00 - Online Präsenz -
Datum Zeit Raum
Donnerstag 24.02.2022 16.15-18.00 Uhr --, --
Donnerstag 03.03.2022 16.15-18.00 Uhr --, --
Donnerstag 10.03.2022 16.15-18.00 Uhr Fasnachtsferien
Donnerstag 17.03.2022 16.15-18.00 Uhr --, --
Donnerstag 24.03.2022 16.15-18.00 Uhr --, --
Donnerstag 31.03.2022 16.15-18.00 Uhr --, --
Donnerstag 07.04.2022 16.15-18.00 Uhr --, --
Donnerstag 14.04.2022 16.15-18.00 Uhr Ostern
Donnerstag 21.04.2022 16.15-18.00 Uhr --, --
Donnerstag 28.04.2022 16.15-18.00 Uhr --, --
Donnerstag 05.05.2022 16.15-18.00 Uhr --, --
Donnerstag 12.05.2022 16.15-18.00 Uhr --, --
Donnerstag 19.05.2022 16.15-18.00 Uhr --, --
Donnerstag 26.05.2022 16.15-18.00 Uhr Auffahrt
Donnerstag 02.06.2022 16.15-18.00 Uhr --, --
Module Doktorat Informatik: Empfehlungen (Promotionsfach Informatik)
Leistungsüberprüfung Lehrveranst.-begleitend
Hinweise zur Leistungsüberprüfung To obtain credit, participants need to:
* read the book chapters discussed in the seminar
* participate in the seminar sessions
* lead 1-3 seminar sessions, including setting homework assignments
* solve homework assignments
* give peer review feedback on the homework of other participants

Participants can miss up to two seminar sessions without failing the course.
An-/Abmeldung zur Leistungsüberprüfung An-/Abmelden: Belegen resp. Stornieren der Belegung via MOnA
Wiederholungsprüfung keine Wiederholungsprüfung
Skala Pass / Fail
Wiederholtes Belegen beliebig wiederholbar
Zuständige Fakultät Philosophisch-Naturwissenschaftliche Fakultät, studiendekanat-philnat@unibas.ch
Anbietende Organisationseinheit Fachbereich Informatik