Computational Complexity Jan-April 2014
Professor Jonathan Katz (Maryland) lecture notes here Professor Luca Trevisan's (UC Berkely/Stanford)lecture notes hereProfessor Sanjeev Arora's (Princeton) Book can be downloaded from here
Professor Jaikumar Radhakrishnan (TIFR Mumbai) Lecture notes here
Professor Oded Goldreich (Weizmann Institute) Lecture notes here
A nice article by Scott Aaronson
Assignment I when the course was offered in 2007
Assignment II when the course was offered in 2007
A O(n log n) Turing Machine to accept strings of two power n zeroes
Any non-regular language needs at-least O(log log n) space to recognize (Seminar Slides by Govind R.) PSPACE Completeness (Seminar Slides by Thejus Gore) P Completeness (Seminar Slides by Simon Samuel) Lecture notes on 2 DFA (Prof. Dexter C. Kozen) Lecture notes on Myhill Nerorde Theorem (Prof. Dexter C. Kozen) Lecture notes on NP-completeness of Hamiltonian Path (Prof. Wing Kai) Results in Circuit complexity - Seminar Slides of Suresh Alternating Space and Time - Seminar Slides of Aswathy and Subisha Arthur-Merlin Protocols - I (Prof. Joan Katz) Arthur-Merlin Protocols - II (Prof. Joan Katz) IMPORTANT FOR EXAM: Notes on Self Reducibility of SAT (Prof. Jayalal Sharma, IIT Madras)