INSTRUCTOR: Anna Gál
TIME/PLACE: TTh 12:30 pm 2:00 pm, TAY 3.144
This course provides a general, graduate level introduction to the theory of computation.
We will use the book "Computational Complexity" by Christos Papadimitriou. The course will cover approximately the first 15 chapters of the book, including the following topics: Models of computation, relations between complexity classes, reductions and completeness, NP-complete problems, randomized computation, cryptography, approximability, circuit complexity, parallel computation. The lectures will also cover material that is not in the book.
PREREQUISITES: Graduate standing and either CS 353 or CS 357 (or an equivalent course) or consent of instructor.