Classes will be held from 10:00-11.20 in ECE 003.
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, advice and interaction, 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 : Mitali Bafna
- TAs : Owen Boseley, Bohan Zhao
- Discussion Board : Link
- Gradescope : Link
- Office Hours : Mitali (Mon 4:00pm-5:00pm, Gates 211), Owen (Fri 10:00am-11:30am, 12:30pm-1:30pm CSE1 Floor 2 Breakout), Bryan (Thurs 3:30-4:30PM CSE1 218)
- Grades : The class will involve biweekly homework (50%), a midterm (20%), and a final exam (30%). Collaboration is allowed on the homework, but you must write-up solutions by yourself. You can submit one of the homeworks a day late with no penalty. You can get up to 2 late days per homework, with 10% off your grade per day (excluding the freebee).
- Sections : If student interest permits, we will host some sections for practice problems, review, and more 431 fun! TBD
- Course Materials : All material covered in this course will be posted in the form of lecture notes and homework pdfs on this website (see the Schedule tab), along with suggested readings. You can also refer to this textbook by Arora and Barak (note that this is a draft copy).