Scribe Notes
Scribe notes will be produced be a student after each lecture. To sign up to scribe a lecture send me an email. For a uniform appearence, please typeset the notes using the following LaTeX file. LaTeX include file. Example file. To make all benefit the most from these scribe notes, it is important that they are produced quickly after each lecture.- For the Wednesday lecture, have the draft ready the following Monday.
- For the Friday lecture, have the draft ready the following Tuesday.
| No | Date | Title | Scribe |
|---|---|---|---|
| 1 | August 25 | Time Complexity (source files) | Søren Valentin Haagerup |
| 2 | August 27 | Tape reduction and Time Hierarchy(source files) | Andreas Hummelshøj Jakobsen |
| 3 | September 1 | Nondeterminism and Space Complexity(source files) | Mikael Harkjær Møller |
| 4 | September 3 | Space and Time(source files) | Camilla Lodahl Gravgaard |
| 5 | September 8 | Logspace reductions and completeness(source files) | Claes Højer Jensen |
| 6 | September 10 | Alternation(source files) | Jesper Broni Andersen |
| 7 | September 15 | Polynomial time hierarchy(source files) | Mads Chr. Olesen |
| 8 | September 17 | Randomized computation(source files) | Søren Valentin Haagerup |
| 9 | September 22 | Connecting PH, P/poly and BPP(source files) | Martin Sergio Hedevang Fæster |
| 10 | September 24 | Counting complexity(source files) | Camilla Lodahl Gravgaard |
| 11 | September 29 | Valiant-Vazirani and Toda's Theorem(source files) | Andreas Hummelshøj Jakobsen |
| 12 | October 1 | Toda's Theorem. Parallel Computation and Circuits(source files) | Mads Chr. Olesen |
| 13 | October 6 | Basic circuit constructions.(source files) | Mikael Harkjær Møller |
| 14 | October 8 | Razborov-Smolensky Circuit Lower Bound(source files) | Jesper Broni Andersen |
| 15 | October 29 | Circuits and Branching Programs(source files) | Martin Sergio Hedevang Fæster |
| 16 | November 3 | Barrington's Theorem(source files) | Claes Højer Jensen |
| 17 | November 5 | Interactive Proofs.(source files) | Søren Valentin Haagerup |
| 18 | November 10 | IP=PSPACE. Arthur-Merlin Games.(source files) | Andreas Hummelshøj Jakobsen |
| 19 | November 12 | Expander Graphs.(source files) | Jesper Broni Andersen |
| 20 | November 17 | Error reduction and derandomization.(source files) | Camilla Lodahl Gravgaard |
| 21 | November 24 | Derandomization using PRG's(source files) | Kristoffer Arnsfelt Hansen |
| 22 | November 26 | Nisan-Wigderson PRG(source files) | Kristoffer Arnsfelt Hansen |
| 23 | December 1 | Hardness Amplification(source files) | Allan Rasmussen |
| 24 | December 3 | Probabilistically Checkable Proofs(source files) | Claes Højer Jensen |
| 25 | December 8 | PCP based on Linearity Testing(source files) | Allan Rasmussen |
| 26 | December 10 | PCP: Overview, degree reduction(source files) | Martin Sergio Hedevang Fæster |
| 27 | December 15 | PCP: Gap amplification(source files) | Allan Rasmussen |