2000 Advanced Complexity Lecture Notes
Here are the of lecture notes from 2000.
Most require the file preamble.tex.
Last year, Rob Ragno write a nice
explanation of how to use preamble.tex.

Lecture 1 (2/1/2000), and also the
Latex version of lecture 1.

Lecture 2, (2/3/2000) and also

Lecture 3, (2/8/2000) and also the
Latex version of lecture 3.

Lecture 4, (2/10/2000) and also the
Latex version of lecture 4.

Lecture 5, (2/15/2000) and also the
Latex version of lecture 5.
 Lecture 6 was on 2/17/2000. We proved that there
exist oracles relative to which P = NP and P /neq NP.
Also introduced randomized computation.
 No class on 2/22/00

Lecture 7, (2/24/2000) and also the
Tex version of lecture 7.

Lecture 8, (2/29/2000), on ValiantVazirani and also the
Tex version of lecture 8.

Lecture 9, (3/2/2000), on Toda's Theorem and also the
Tex version of lecture 9.

Lecture 10, (3/7/2000), a proof that parith is not in AC0 and also the
Tex version of lecture 10.

Lecture 11, (3/9/2000), on Toda's Theorem and an oracle
separating PH from PSPACE and also the

Lecture 12, (3/14/2000),

Lecture 13, (3/16/2000), Parity is not in AC0, and the
LaTex version of lecture 13.

Lecture 14, (3/28/2000), on Razborov's Thm, and the
LaTex version of lecture 14.

Lecture 15, (3/30/2000) and the
LaTex version of lecture 15.

Lecture 17 (4/6/2000) , and the
LaTex version of lecture 17.

Lecture 18 (4/11/2000) , and the
LaTex version of lecture 18.

Lecture 19 (4/13/2000) , and the
LaTex version of lecture 19.

Lecture 20 (4/20/2000), and the
LaTex version of lecture 20.

Lecture 21, and the
LaTex version of lecture 21.

Lecture 22, and the
LaTex version of lecture 22.
Daniel A. Spielman
Last modified: Sun Apr 1 17:28:43 2001