Theory of Computation

Prerequisites & course information

Examine polynomial hierarchy, circuit lower bounds, randomized computation, approximability, communication complexity, pseudorandom generators, and probabilistically checkable proofs. Three lecture hours a week for one semester.