<p>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.</p>

General Catalog

Current Topics in Computer Theory: Complexity Theory

COM SCI 289CO

4 units