Oberwolfach Meeting on Complexity Theory (Nov. 2009)
Organizers:
Peter Buergisser,
Joachim von zur Gathen,
Oded Goldreich,
and Madhu Sudan.
Some of the presentations are available below.
- Scott Aaronson, Efficient Simulation of Quantum Mechanics
Collapses the Polynomial Hierarchy (joint with Alex Arkhipov),
PPT.
- Mark Braverman, Poly-logarithmic independence fools AC0 circuits,
PDF.
- Peter Bürgisser, Overview of Geometric Complexity Theory,
PDF
- Zeev Dvir, From Randomness Extraction to Rotating Needles.
PDF.
- Oded Goldreich, Complexity Theoretic Aspects of Property Testing,
HTML
- Iftach Haitner, A Parallel Repetition Theorem for Any Interactive Argument,
PDF.
- Valentine Kabanets, Direct Product: Decoding and Testing,
PPT.
- Pavel Pudlak (joint work with Mohan Paturi),
Complexity of Circuit Satisfiability,
PDF.
- Amir Shpilka, Recent Results on Polynomial Identity Testing,
PDF
- Madhu Sudan, Universal Semantic Communication,
Powerpoint Show
- Chris Umans (joint work with Kiran Kedlaya),
Fast Polynomial Factorization and Modular Composition,
PPT
- Salil Vadhan, Inaccessible Entropy,
pptx.
current MFO meeting webpage and
Oded Goldreich's homepage.