Computational Complexity Theory
Prerequisites include basic courses on algorithms, discrete maths, and theory
of computing. In particular, please brush up a few topics like asymptotic notation,
Turing machines, NP-completeness, and basic probability theory.
We will follow the book by Sanjeev Arora and Boaz Barak, and will try to
cover part 1 of it. I may add/delete some topics as we go on.
There are several online lecture notes. I will mention appropriate references
from time to time.
- Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak
- Computational Complexity by Christos Papadimitriou
- Introduction to the Theory of Computation by Michael Sipser
There will be two assignments, midsem, and endsem. In addition to this, there
will be a project where you will be assigned paper(s) to read. You will have to
give a 30 minutes presentation on your project.
The weightage is as follows:
- Assignments: 20
- Midsem: 20
- Endsem: 40
- Project: 20
While solving the assignments (and exams too!), you are not
supposed to discuss with anyone (neither in your class nor anyone else).
If at all you discuss an assignment problem
with someone, name of that person should be mentioned while writing the
solution of that particular problem. If you look up the solution on the
Internet, the link to the solution should also be mentioned while writing it.
Any other form of copying implies a fail grade in the course.
If you get stuck while solving
the assignment, you are welcome to discuss with me.
There are problem sets which you need not submit and
are free to discuss with each other.
Note: Please read the Copying policy before you start
solving the assignment. The solutions/hints will be posted on the
deadline. Hence no late submissions are allowed.
Topics covered so far:
- 4th Jan: Introduction to computational complexity, Turing machines,
Universal Turing machine, introduction to some complexity classes like
P,NP,EXP,NEXP,PSPACE,L,NL and their relationship.
8,11 Jan: no class
- 15th Jan: NP-completeness, Cook-Levin theorem
- 18th Jan: Parsimonious reductions, Levin reductions, Decision vs search,
Deterministic time hierarchy theorem
- 22nd Jan: Non-deterministic time hierarchy theorem (see this and this for some details of the proof)
- 25th Jan: Baker-Gill-Solovay theorem
- 29th Jan: Space-bounded computation: Introduction and examples of logspace
algorithms, NL algorithm for
directed reachability, Savitch's theorem
- 1st Feb: Directed reachability is NL-complete, Immerman-Szelepcsenyi theorem
(Ref: Section 4 of this
- 5th Feb: Immerman-Szelepcsenyi theorem continued
- 8th Feb: Polynomial time hierarchy
- 12th Feb: Polynomial time hierarchy, RL algorithm for undirected reachability
- 15th Feb: Probabilistic TMs, BPP and RP, containments of complexity classes
- 19th Feb: Error reduction in BPP, Sipser-Gacs theorem
- 22nd Feb: Problem solving session, midsem
- 5th March: Circuit complexity: P/poly, uniformity, Karp-Lipton theorem
- 8th March: Meyer's theorem, existence of hard functions, NC and AC classes, non-uniform hierarchy theorem
- 12th March: BPP and P/poly, Interactive proofs: introduction, interactive protocol for GNI
- 15th March: AM, public coins interactive protocol for GNI
- 19th March: IP=PSPACE
- 22nd March: IP=PSPACE continued, introduction to counting: the class \#P
- 26th March: PP, \#P-completeness, Valiant-Vazirani theorem
- 2nd April: Toda's theorem
- 5th April (2 classes): Toda's theorem continued, Derandomization: error-reduction using expanders (deterministic) (Ref)
- 9th April: Probabilistic error reduction using expanders Ref
- 11th April (extra class):Pseudorandomness: PRG for space-bounded computation: INW generator (Ref
- 12th April: Parity not in AC0 (Ref)
- 16th April: Parity not in AC0 continued, Undirected s-t connectivity in logspace (Ref)