 | | | | |
Home»Graduate Education»Courses»Graduate Course Descriptions»CSE201A
| | | | | Graduate Course Descriptions
CSE201A - Advanced Complexity
(New Fall 2002)
Units: 4
Course Description:
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
| | | back to top ^ |
| |
