CSE104 - Computational Complexity
Course Basics
Class: Mo/We, 7:10PM - 8:45PM
Instructor: C. (Sesh) Seshadhri (sesh@)
Office hours: Tue, 11-12
Piazza: Piazza link
Course Description
Introduction to computational complexity. We will cover the basics of time complexity, NP-completeness, space complexity, the polynomial hierarchy, and possibly
randomized complexity classes. Students should be familiar with the content of CSE103 (basic theory of computation), and must be comfortable in writing proofs
in Latex.
Course Textbook
We will follow Computational Complexity: A Modern Approach by Arora and Barak.
A draft of the book is also publicly available.
The material in the beginning lectures is also covered in the latter part of
Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani, and Ullman.