Computational Complexity Theory, Fall 2008
CT08 / 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. To facilitate this I request that a draft version is produced as soon as possible followed by a complete version. Send both versions to me such that I can place them on the course web site. Please send the LaTeX source as well as a compiled pdf file.

  • For the Wednesday lecture, have the draft ready the following Friday at the latest and have the complete version ready by the following Tuesday.
  • For the Friday lecture, have the draft ready the following Tuesday at the latest and have the complete version ready by the following Thursday.
You are encouraged to comments on each others scribe notes.

The notes have been lightly edited. (Thanks to Casper Kejlberg-Rasmussen and Rasmus Ibsen-Jensen for assistance).

Bugs can clearly still be present.

No Date Title Scribe
1August 27 Time Complexity (source file) Kasper Borup
2August 29 Space Complexity (source file) Rocío Santillán Rodríguez
3September 3 Space bounded function computation (source file) Jonas Bæklund
4September 5 Alternation, Polynomial Time Hierarchy (source file) Jakob Truelsen
5September 10 Oracle Turing Machines(source file) Casper Kejlberg-Rasmussen
6September 12 Time-space lower bounds for SAT, etc.(source file) Karsken Bælg
7September 24 Parallel Computation (source file) Rasmus Ibsen-Jensen
8September 26 Threshold Circuits and Multiplication (source file) Michael Kølbæk Madsen
9October 1 Switching lemma and lower bounds for AC0 (source file) Thomas Dueholm Hansen
10October 3 The Razborov-Smolensky Circuit Lower Bound (source file) Claus Thrane
11October 8 Randomized computation (source file) David Kjær
12October 10 BPP in PH, BPL, Random walks and USTCON (source file) Mark Greve
13November 5 Random walks and expanders (source file) Rasmus Ibsen-Jensen
14November 7 Error reduction using expanders. USTCON in L. (source file) Jakob Truelsen
15November 12 USTCON in L. Derandomization using PRG's. (source file) Michael Kølbæk Madsen
16November 14 Derandomization and Nisan-Wigderson PRG. (source file) David Kjær
17November 19 Nisan-Wigderson PRG. Error correcting codes. (source file) Rocío Santillán Rodríguez
18November 21 Error correcting codes. Local decoding and hardness amplification. (source file) Thomas Dueholm Hansen
19November 26 Local decoding, list decoding and hardness amplification. (source file) Claus Thrane
20November 28 Interactive proofs. IP=PSPACE. (source file) Kasper Borup
21December 3 Probabilistically Checkable Proofs. NP is in PCP(nO(1),O(1)). (source file) Mark Greve
22December 5 Linearity Testing. PCP: Overview and degree reduction. (source file) Casper Kejlberg-Rasmussen
23December 10 PCP: Gap amplification. (source file) Kristoffer Arnsfelt Hansen
24December 12 PCP: Alphabet reduction (source file) Kristoffer Arnsfelt Hansen

Valid HTML 4.01!