Time and Topics
Time and modalities:
- Time: March 8 and 9
- Rooms: SR 016 in E1 3 (March 8), HS003 in E1 3 (March 9)
- Every participant is supposed to give a talk of about 90 mins.
- Proofs should be done on the blackboard, slides can be used in addition for definitions, statement of theorems etc.
Potential topics:
- The Nisan-Wigderson generator (Arora & Barak, Sections 20.1, 20.2, lecture notes available)
- Expander graphs and space efficient algorithms for undirected connectivity (Arora Barak, Sections 21.1 - 21.4, lecture notes available).
- Communication Complexity (Arora & Barak, Chapter 13) -> Julian Baldus
- Proof Complexity (Arora & Barak, Chapter 15, maybe further material needed)
- Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
- Quantum computation and Grover's algorithm (Arora & Barak, Sections 10.1 - 10.4, Schöning Chapter 26) -> Nico Mansion
- Closure Properties of #P (Hemaspaandra & Ogihara, Chapter 5) -> Hadar Manor
Arora & Barak, Computational Complexity - A Modern Approach, Cambridge University Press.
Schöning, Gems of Theoretical Computer Science, Springer
Hemaspaandra & Ogihara, The Complexity Theory Companion, Springer