Graduate Course Descriptions

Select a Course CSE200CSE201ACSE202CSE203ACSE204ACSE205ACSE206ACSE207CSE208CSE209ACSE209BCSE210CSE211CSE218CSE221CSE222ACSE222BCSE223ACSE223BCSE224CSE225CSE226CSE227CSE228CSE229ACSE229BCSE229CCSE230CSE231CSE232CSE232BCSE233CSE237ACSE237BCSE237CCSE237DCSE238CSE240ACSE240BCSE240CCSE240DCSE241ACSE242ACSE243ACSE244ACSE244BCSE245CSE246CSE247CSE248CSE249ACSE249BCSE249CCSE250ACSE250BCSE251CSE252ACSE252BCSE252CCSE253CSE254CSE255CSE256CSE257CSE257ACSE258ACSE259CSE260CSE261CSE262CSE268ACSE268CCSE269CSE270CSE271CSE272CSE275CSE280ACSE280BCSE282CSE283CSE290CSE291CSE292CSE293CSE294CSE298CSE299CSE500CSE501CSE599

CSE201A – Advanced Complexity

Units: 4

Course Objectives:

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.

Format:

Prerequisites:
CSE 200

Other restrictions:

Example Textbook(s):

Laboratory work:

Offered: