1998 Advanced Complexity Lecture Notes

• Lecture 1, and also the Latex version of lecture 1.

• Lecture 2, and also the Latex version of lecture 2.

  The files used to create this

  • trees.pstex_t (the latex of the figure)
  • trees.pstex (the ps of the figure)
  • trees.fig (the figure file), and
  • the note that Raj included with the files

• Lecture 3, and also the Latex version of lecture 3.

• Lecture 4, and also the Latex version of lecture 4.

• Lecture 5, and also the Latex version of lecture 5.

• Lecture 6, and also the Latex version of lecture 6.

• Lecture 7, and also the Latex version of lecture 7.

• Lecture 8, and also the Latex version of lecture 8.

• Lecture 9, and also the Latex version of lecture 9.

• Lecture 10, and also the Latex version of lecture 10.

• Lecture 11, and also the Latex version of lecture 11.

• Lecture 13, and also the Latex version of lecture 13.

• Lecture 14, and also the Latex version of lecture 14.

• Lecture 15, and also the Latex version of lecture 15.

• Lecture 17, and also the Latex version of lecture 17.

• Lecture 18, and also the Latex version of lecture 18.

• Lecture 19.

• Lecture 20, and also the Latex version of lecture 20.

• Lecture 21, and also the Latex version of lecture 21.

• Sample LaTeX files for those who want pointers. This page also contains the LaTeX files for the old lecture notes.
• Lecture 1 - Time, Space, Reductions, Completeness, NP, CVP, PH. The latex file is here.
• Lecture 3 - Alternation The latex file is here.
• Lecture 4 - NC, Parallel Computation, NC vs. P The latex file is here.
• Lecture 5 - P/poly, and relation to NP. Self reducibility The latex file is here.
• Lecture 6 - The latex file is here.
• Lecture 7 - The latex file is here.
• Lecture 8 The latex file is here.
• Lecture 10, on Toda's theorem The latex file is here.
• Lecture 11, on Toda's Theorem The latex file is here.
• Lecture 12, Parity cannot be computed in AC_0 The latex file is here.
• Lecture 14, Razborov's theorem The latex file is here.
• Lecture 15, Razborov's theorem The latex file is here.
• Lecture 17, Public Coins = Private Coins The latex file is here.
• Lecture 18, Public Coins = Private Coins The latex file is here.