Units:
4
Poly-time hierarchy; BPP in \Sigma_2^P; NSPACE(f(n)) in SPACE(f(n)^2); NL=coNL; non-uniform and circuit complexity; some circuit lower bounds; IP=PSPACE; PCP; Application of PCP to approximation hardness; Complexity of proof systems; Parallel complexity classes NC and AC; P-completeness; hardness versus randomness; pseudorandomness.
Prerequisites:
CSE 200
New Fall 2002