Summer 2010
Computational Complexity
Class hours: Mondays 14:15-15:45. Approval talks: 12:30-14:00
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 |
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner