Loading prerequisite graph...
COM SCI 289CO
Current Topics in Computer Theory: Complexity Theory
4 units
Taken?
Description
Lecture, four hours; outside study, eight hours. Diagonalization, polynomial-time hierarchy, PCP theorem, randomness and de-randomization, circuit complexity, attempts and limitations to proving P does not equal NP, average-case complexity, one-way functions, hardness amplification. Problem sets and presentation of previous and original research related to course topics. Letter grading.
Click on any course to view its details