Computational Complexity Theory - Monsoon 2018

Credits: 4

Pre-requisites: Algorithms, Discrete Maths, Theory of Computing, Probability

Post-conditions: Upon successful completion of the course, the student will gain the following:
  • knowledge of different models of computation and their relationships

  • ability to bound resource usage (e.g., time, space, circuit size, depth) required for problems under different models of computation

  • ability to place a problem in the hierarchy of computational complexity classes

  • ability to show separations, collapses of classes and prove completeness of problems

  • understand the major questions (e.g., P =? NP) and their role in other fields of computer science

  • (if time & scope permits) develop knowledge of randomized complexity classes and ability to perform randomized reductions


Computational problems can be studied from the point of view of computational resources (e.g., running time) required to solve them – this forms the notional of computational difficulty. Apart from the nature of the problem, the difficulty also depends on the underlying model of computation. Problems can be related to each other based on their resource usage, and problems with similar difficulty can be grouped together to form a classification of computational problems into complexity classes.

Computational complexity is about studying the above concepts, and is especially concerned with giving precise upper and lower bound on the amount of resources required to solve certain problems. This has had a profound impact on current algorithm design and cryptography, and still sees applications in areas outside of theoretical computer science.

Paper Reading:


Lectures will follow a mixture of regular lectures and flipped-classroom model. Hence, maturity in logic and reasoning is mandatory. The course will start where a standard course on Theory of Computation ends, hence it is strongly advisable that students are comfortable and strong in TOC.

  • [AB] Sanjeev Arora and Boaz Barak. “Complexity Theory: A Modern Approach”
  • (Reference) [S] Michael Sipser, “Introduction to the Theory of Computation”
Evaluation: 75% exams, 25% course-work and home-work
  • 40% final exam
  • 30% mid-sem
  • 5% quiz / scribe (see below)
  • 18% homework (1% for each homework problem, lowest 15% problems to be dropped)
  • 5% paper reading (to be decided after mid-sem exam)
  • 2% - free (thanks for attending the course)

Tentative schedule

 Lecture Topics Chapter
 Lec 1,2Det. Turing machine definition
Linear speedup
Palindrome lower bound
AB1  Lec0 Lec1
Lec2 by Parth
 Lec 3NDTM tape reduction, linear speedupLec3 by Siddhartha
 Lec 4Space complexity, space compression, time and space simulations.
Hierarchy of common complexity classes.
Lec4 by Lavina
 Lec 5Non-deterministic space classes, Savitch's theoremLec5 by Hanit
 Lec 6Sub-logarithmic space TMsLec6
 Lec 7Reduction, Complete problemsLec7 by Niket
 Lec 8Paper discussion: DTIME^1(o(n log n)) = REG, Tally languages, Padding techniques, Log-space reduction, complete problemsTheorem 3.3 in Koboyashi1985
Lec8 (pending)
 Lec 9Space hierarchy theoremLec9 by Sushant
 Lec10Time hierarchy theorem, NDTM hierarchy theoremAB3 Lec10 by Harshit
 Lec11Turing reduction, BGS theoremAB3 Lec11 by Siddharth 
 Lec12Ladner's theorem Lec12 AB3 
 Lec13PH AB5
 Lec14Paper presentation by Siddhartha & Hanit Paper
 Lec15PH-completeness and coNL-completeness AB4, AB5
 Lec16NL and coNL. Boolean circuit complexity.AB4, AB6 
 Lec18Circuit size upper bounds and Shannon lower bound, Karp-LiptonAB6
 Lec19Paper presentation by Varun Paper
 Lec20Size-hierarchy theorem, Kannan's theorem AB6 notes by Paul Beame
 Lec21Paper presentation by ParthPaper
 Lec22NC and AC circuit classes AB6 
 Lec23NC and Logspace classes, Furst-Saxe-SipserAB6
 Lec24Probabilistic complexity classesAB7.1,7.3 
 Lec25Paper presentation by NiketPaper 
 Lec26Paper presentation by SushantPaper 

Scribe instructions

Rename ex.tex to LecXX.tex. Do not modify preamble.tex.
Try to present the results as reusable lemma/theorem/etc. and use figures if that improve clarity (use ipe/xfig/etc. pdf-producing WYSIWIG tools).
Subpages (1): Scribes
Debajyoti Bera,
Aug 18, 2018, 11:08 AM
Debajyoti Bera,
Sep 4, 2018, 2:51 AM