2000 Advanced Complexity Lecture Notes

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

• Lecture 2, (2/3/2000) and also
  • the Latex version of lecture 2.
  • the file npmach.eps
  • the file altmach.eps

• 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 Valiant-Vazirani 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
  • Tex version of lecture 11.
  • The first figure.
  • The second figure
  • The third figure
  • The fourth figure

• 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.