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:

 

  1. The Nisan-Wigderson generator (Arora & Barak, Sections 20.1, 20.2, lecture notes available)
  2. Expander graphs and space efficient algorithms for undirected connectivity (Arora Barak, Sections 21.1 - 21.4, lecture notes available).
  3. Communication Complexity (Arora & Barak, Chapter 13) -> Julian Baldus
  4. Proof Complexity (Arora & Barak, Chapter 15, maybe further material needed)
  5. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
  6. Quantum computation and Grover's algorithm (Arora & Barak, Sections 10.1 - 10.4, Schöning Chapter 26) -> Nico Mansion
  7. 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

 

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.