II Semester 2018-19

Computer Science and Engineering

514 Rajeev Motwani Building

rtewari[at]cse[dot]iitk[dot]ac[dot]in

**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 |

- Some instructions on how to scribe lecture notes

[tex][pdf] - Template and other essential files for scribing (read the
instructions carefully before proceeding)

[single zipped file] - The lecture notes posted below are as submitted by the students. They have not been verified by the instructor for correctness and may contain errors.

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 |