Zurück zur Auswahl
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. |
| Teilnahmevoraussetzungen | 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 | Wochentag | Zeit | Raum |
|---|---|---|---|
| wöchentlich | Donnerstag | 16.15-18.00 | - Online Präsenz - |
Einzeltermine
| 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) |
| Prüfung | Lehrveranst.-begleitend |
| Hinweise zur Prü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 Prüfung | Anm.: Belegen Lehrveranstaltung; Abm.: stornieren |
| Wiederholungsprüfung | keine Wiederholungsprüfung |
| Skala | Pass / Fail |
| Belegen bei Nichtbestehen | beliebig wiederholbar |
| Zuständige Fakultät | Philosophisch-Naturwissenschaftliche Fakultät, studiendekanat-philnat@unibas.ch |
| Anbietende Organisationseinheit | Fachbereich Informatik |