Time:
Tue: 10:30 - 11:45 am
Thu: 12:00 - 01:15 pm
Place: KD103
TA:
Chetan Gupta (CSE id: gchetan)
Course Textbook: Computational Complexity: A Modern Approach
by Sanjeev Arora and Boaz Barak.
| No. | Topic | Group | Presentation Schedule |
| 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] |
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 |