CS 721 Introduction to Computational Complexity

Course Instructor: Nutan Limaye

Course Name : CS 721 Introduction to Computational Complexity

Course Type: Honours / Elective

Prerequisite: 

No formal prerequisite but the CS undergrads would already have done the course Automata Theory and Logic ( which covers Turing machines). Also, a foundation on data structures and algorithms would be necessary to appreciate this course. A little bit of abstract algebra (finite groups and fields), graph theory, and probability was covered quickly in the first lecture (so basically assumed).

Course Content:

Boolean circuits and formulas: lower bounds on circuit sizes. Turing machines and the notion of algorithms and computability. Time complexity: Time heirarchy theorem, P and NP, coNP, NP completeness and NP hardness, Cook-Levin theorem.

Space complexity: Relation with time complexity classes, L, NL, PSPACE, NPSPACE, Savitch’s theorem, Immerman-Szelepcsenyi (only roughly sketched). Randomness as a resource: BPP and RP Interaction as a resource: Completeness and soundness, private and public coins, IP, MA and AM.

After midsem: Arithmetic circuits, VP, VNP Structural results for arithmetic circuits Arithmetic circuit and formula lower bounds (most results only roughly sketched)

Book & Online Material:

The book by Michael Sipser is easy to follow but is not enough. The book by Sanjeev Arora and Boaz Barak (which is also freely available) is the source for the instructor's notes and thoroughly covers the topics done in class.

Course Structure:

1. No attendance requirements. All the instruction was done via the whiteboard. The Prof. was really good and would answer all questions well. The course is not straightforward mathematics and it takes a lot of time to familiarize oneself with and appreciate the results. Logical pitfalls are common and sometimes you might think you have come up with an algorithm that beats a result. Because of all this attending classes is highly recommended (even though the Prof has prepared a set of notes that she uploads on moodle and follows for the pre-midsem part).
2. Apart from the midsem and the endsem a small quiz of 2 marks was taken every week. Also, after the midsem each student or a group of two students had to present a seminar on some advanced topic of their choice. 
The weightages were not disclosed but... as the endsem covered both pre-midsem and post-midsem equally it is better to focus on pre-midsem.
3. We had around 7 graded assignments. Two of which had to be submitted electronically on a LATEX file.
4. In groups of two students were supposed to give seminars on topics of their choice. These were also graded. Topics included: Communication complexity, cost of generating true randomness, quantum complexity classes, etc.

Pro Tips:

Attend classes, ask questions. Prof. Limaye used to come to the classroom half an hour before each lecture to resolve doubts so make use of that. Also reading Arora-Barak was necessary for me to keep up.

Personal Comments:

Post-midsem was a mess. No good reference materials and very heavy mathematics so I chilled out but it did not affect my grade very badly.

Respondent: Abhijeet Melkani