Forschungsinstitut für Diskrete Mathematik

Graduate Seminar on Discrete Optimization (S4C1)

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

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. T. Nieberg,
Dr. U. Brenner