INSTRUCTOR: Anna Gál
TIME/PLACE: TTh 12:30 pm 2:00 pm, RLM 7.120
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 CS 353 (or an equivalent course), or consent of instructor.