Computational Complexity is the mathematical investigation of several broad questions that have to do with computation. In this class, we shall develop the mathematics required to ask:
- What is hard to compute and why?
- How useful is access to various resources like time, memory, randomness and advice, when it comes to computation?
We seek to give a rigorous mathematical framework that will enable us to answer some of these questions. Along the way, we shall encounter several interesting mathematical tools. 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.
Logistics
- Professor: Anup Rao, TAs: Sivaramakrishnan Natarajan Ramamoorthy, Yuqing Ai.
- Time and Location: Tuesdays and Thursdays 10-11:20 in EEB 037.
- Office Hours: Anup from 3:30-4:30 on Tuesdays in CSE 656. Siva from 2-3 on Thursdays in CSE 4th floor breakout area, Yuqing from 3:30-4:30 on Wednesdays in CSE 5th floor breakout area.
- Work: The class willl involve biweekly homework (50%), a take home midterm (20%), and an in-class final exam (30%). Collaboration is allowed on the homework, but you must write-up solutions by yourself.
- Course Materials: All material covered in this course will be posted in the form of lecture notes on this website (see the Schedule and Notes tab). You can also refer to this textbook by Arora and Barak.