Computational Complexity Theory

• Instructors : Chandan Saha   Course number and Credits : E0 224 and 3:1   Lecture time : M,W 11:00-12:30   Venue : CSA 117


• TA : Palash Dey


• Objective : Computational complexity theory is the fundamental subject of classifying computational problems based on their `complexities'. In this context, `complexity' of a problem is a measure of the amount of resources (time/space/random bits/queries etc.) used by the best possible algorithm that solves the problem. The aim of this course is to give a basic introduction to this field. Starting with the basic definitions and properties, we intend to cover some of the classical results and proof techniques of complexity theory.


• Syllabus (tentative):
  • Turing machines - a computational model
  • P, NP and NP-completeness
  • Diagonalization and Relativization
  • Space complexity
  • Polynomial time hierarchy
  • Boolean circuits
  • Randomized computation
  • Interactive proofs
  • Introduction to PCP theorem and hardness of approximation
  • Complexity of counting


• References :
  1. Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak
  (We'll closely follow this book)
  2. Computational Complexity Theory by Steven Rudich and Avi Wigderson (Editors)
  3. Gems of Theoretical Computer Science by Schoening and Pruim
  4. The Nature of Computation by Moore and Mertens
  5. The Complexity Theory Companion by Hemaspaandra and Ogihara
  6. Online lecture notes... (take a look at this webpage)
  
  
• Prerequisites : Basic familiarity with undergraduate level theory of computation and data structures & algorithms would be helpful. More importantly, we expect some mathematical maturity with an inclination towards theoretical computer science.


• Grading policy :
  • Assignments - 30%
  • Mid-term exam - 25%
  • End-term exam - 25%
  • Scribing lecture notes - 20%


• Announcements:
  • Mid-term exam on September 29, 2014 (Monday). Time: 11:00-13:00. Venue: CSA 117
  • Neeldhara Misra has offered a couple of lectures (14 & 15) on Boolean circuits. Please find the slides and lecture note prepared by her below.
  • End-term exam on December 10, 2014 (Wednesday). Time: 10:00-13:00. Venue: CSA 117


• Assignments :
  • Assignment 1 (due date: Sep 12, 2014)
  • Assignment 2 (due date: Oct 24, 2014)
  • Assignment 3 (due date: Nov 25, 2014)


• Lectures (unedited notes scribed by students):
  • Lecture 1: Introduction to the course
  • Lecture 2: Turing machines
  • Lecture 3: Complexity classes: DTIME, P and NP
  • Lecture 4: NP-completeness: Cook-Levin theorem
  • Lecture 5: Some NP-complete problems
  • Lecture 6: Coping with NP-completeness; Search versus Decision
  • Lecture 7: Diagonalization: Time hierarchy, Ladner's theorem
  • Lecture 8: Oracle Turing machines; Baker-Gill-Solovay theorem
  • Lecture 9: Space bounded computation: Complexity classes; Savitch's theorem
  • Lecture 10: PSPACE-completeness; NL-completeness
  • Lecture 11: Log-space reduction; NL-completeness (contd.)
  • Lecture 12: Immerman-Szelepcsenyi theorem; Polynomial hierarchy
  • Lecture 13: Polynomial hierarchy (contd.)
  • Lecture 14: Boolean circuits: Introduction; Class P/poly
  • Lecture 15: Karp-Lipton Theorem; Class NC and AC; P-completeness. [slides]
  • Lecture 16: Some remarks on Boolean circuits
  • Lecture 17: Randomized computation: Class BPP, Polynomial identity testing
  • Lecture 18: BPP = co-BPP; Median finding; Classes RP, co-RP
  • Lecture 19: Class ZPP; Error reduction for BPP; Sipser-Gacs theorem
  • Lecture 20: Class PP; Randomized reduction; Valiant-Vazirani theorem
  • Lecture 21: Randomized space bounded computation; Intro to Interactive Proofs
  • Lecture 22: Classes AM and MA; Graph non-isomorphism in AM
  • Lecture 23: IP in PSPACE; co-NP in IP
  • Lecture 24: TQBF in IP
  • Lecture 25: IP = PSPACE (contd.); Intro to PCP theorem
  • Lecture 26: Equivalence of two views of the PCP theorem; Hardness of approximation of IND-SET
  • Lecture 27: Hardness of approximation of Vertex Cover; Proof of NP in PCP(poly(n),1)
  • Lecture 28: NP in PCP(poly(n),1) contd.; Fourier expansion of boolean functions
  • Lecture 29: Blum-Luby-Rubinfeld linearity test