CS640: Computational Complexity Theory
II Semester 2018-19


Raghunath Tewari
Computer Science and Engineering
514 Rajeev Motwani Building

Course Information

Tue: 10:30 - 11:45 am
Thu: 12:00 - 01:15 pm

Place: KD103

Chetan Gupta (CSE id: gchetan)

Course Textbook: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.


Useful Documents

Course Projects

No. Topic Group Presentation Schedule

Lecture Notes

Lecture No. Date Topic Scribe Lecture Notes
(draft version)
1 8th Jan 2019 Introduction to Computational Complexity Raghunath Tewari [tex][pdf]
2 10th Jan 2019 Introduction to Computational Complexity Deepak Bhati [pdf]
3 15th Jan 2019 Complexity of SAT Darshit Vakil [pdf]
4 17th Jan 2019 Hierarchy Theorems, Space Complexity Desai Aneri Hiren [pdf]
5 22nd Jan 2019 Savitch's Theorem Waseem Akram [pdf]
6 24th Jan 2019 Immerman Szelepscenyi Theorem Priya Purohit [pdf]
7 31st Jan 2019 QBF and Polynomial Hierarchy Nikhil Shagrithaya [pdf]
8 5th Feb 2019 Polynomial Hierarchy Vibhor Porwal [pdf]
9 7th Feb 2019 Time Space Lower Bound and Boolean Circuits Shubham Sharma [pdf]
10 12th Feb 2019 Circuit Complexity Kuldeep Sahu [pdf]
11 13th Feb 2019 Karp-Lipton Theorem and Introduction to Randomized Complexity Raj Kumar Meena [pdf]
12 14th Feb 2019 Randomized Complexity Shaswat Kar [pdf]
13 26th Feb 2019 Sipser-Gacs-Lautemann Theorem Rahul Gupta [pdf]
14 27th Feb 2019 Counting Complexity Rahul Kumar Singh [pdf]
15 28th Feb 2019 Permanent is hard for #P Saiteja Utpala [pdf]
16 5th Mar 2019 Valiant Vazirani Theorem Saiteja Utpala [pdf]
17 12th Mar 2019 Toda's Theorem Desai Aneri Hiren [pdf]
18 26th Mar 2019 Toda's Theorem and Interactive Proofs Shubham Sharma [pdf]
19 28th Mar 2019 Interactive Proofs Priya Purohit [pdf]
20 29th Mar 2019 Arthur Merlin Games Waseem Akram [pdf]
21 2nd Apr 2019 IP = PSPACE Rahul Gupta [pdf]
22 4th Apr 2019 IP = PSPACE (contd) Vibhor Porwal [pdf]
23 9th Apr 2019 Circuit Lower Bound for Parity Raj Kumar Meena [pdf]
24 11th Apr 2019 Communication Complexity Nikhil Shagrithaya [pdf]
25 16th Apr 2019 Probabilistically Checkable Proofs - I Shaswat Kar [pdf]
26 18th Apr 2019 Probabilistically Checkable Proofs - II Deepak Bhati [pdf]

Practice Problems and Assignments

Reading Exercise and Practice Problems (Contains reading exercise and practice problems. This link will keep getting updated as the course progresses.)

Assignment Posting Date Due Date
Assignment 1 12th Feb 26th Feb