This seminar will cover several aspects of computational complexity
including topics like space complexity, boolean circuits, randomized algorithms,
and the PCP theorem.
It is based on the book
Computational Complexity: A Modern Approach by S. Arora and B. Barak
(Cambridge University Press, 2009).
Each talk will summarize one chapter of this book.
Each participant is supposed to be familiar in advance with the basics of
complexity theory as presented in chapters 1 and 2 of the book cited above.
| Number | Approval talk | Talk | Name | Topic | Mentoring |
|---|---|---|---|---|---|
| 1 | 3.5. | 17.5. | Christoph Bachner | Diagonalization (Chapter 3) | Christian Schulte |
| 2 | 10.5. | 31.5. | Sarah Weischer | Space complexity (Chapter 4) | Markus Struzyna |
| 3 | 17.5. | 7.6. | Sarah Weischer | Boolean circuits (Chapter 6) | Markus Struzyna |
| 4 | 31.5. | 14.6. | Christoph Bachner | Randomized computation (Chapter 7) | Christian Schulte |
| 5 | 7.6. | 21.6. | Raoul Venn | Interactive proofs (Chapter 8) | Christoph Bartoschek |
| 6 | 14.6. | 28.6. | Raoul Venn | PCP Theorem and hardness of approximation: an introduction (Chapter 11) | Christoph Bartoschek |
| 7 | 21.6. | 5.7. | Wladimir Kutow | The polynomial hierarchy and alternations (Chapter 5) | Dirk Müller |
| 8 | 28.6. | 12.7. | Wladimir Kutow | Cryptography (Chapter 9) | Dirk Müller |