1998 Advanced Complexity Lecture Notes
Here are a bunch of lecture notes from 1998. Most require the file
preamble.tex
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.
The following lectures from 1997 are also available:
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.
Daniel A. Spielman
Last modified: Tue Apr 13 14:14:07 1999