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.

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