Course Instructor: Anup Rao (email@example.com), office hours: Tuesdays 2:30-3:30 pm, in CSE 656.
TA: Cyrus Rashtchian (firstname.lastname@example.org), office hours: Wednesdays 5-6pm, in CSE 306.
Computational Complexity is the mathematical investigation of several broad questions that have to do with computation. What is computation? What is hard to compute and why? What is easy to compute? How useful is access to various resources like time, memory, randomness and advice?
In this class, we seek to give a rigorous mathematical framework that will enable us to answer some of these questions. We shall explore what is known about the most famous open problem in computer science (the P vs NP question).
Complexity theory has been around as an area for more than 50 years, but it is still in its infancy. It is notorious for generating the hardest open questions in computer science.
The class website is on canvas, where you can access lecture notes, homework and a discussion board.
Grading will be based on biweekly homework, a take-home midterm and an in-class final. Collaboration on the homework is encouraged, but all answers should be written up individually.
Week 1 [3/29, 3/31]
Week 2 [4/5, 4/7]
Week 3 [4/12, 4/14]
Week 4 [4/19, 4/21]
Week 5 [4/26, 4/28]
Week 6 [5/3, 5/5]
Week 7 [5/10, 5/12]
Week 8 [5/17, 5/19]
Week 9 [5/24, 5/26]
Week 10 [5/31, 6/3]