Course Description

Complexity Theory is a subset of Theoretical Computer Science that primarily focuses on proving the nonexistence of efficient algorithms for computational problems, classifying problems based on the amount of resources required to solve them, and comparing different classes of problems.

A few questions that we will explore in this course are:

1. Can you solve every problem if you have unbounded time and space?
2. Are there problems solvable in exponential time that are not solvable in polynomial time?
3. Can randomization give us simpler and more efficient algorithms for some problems?
4. Are there hard problems whose solutions are also hard to verify?
5. Is it possible to make small and efficient silicon chips to solve the famous 3SAT problem when the formula has at most 1000000 variables?

Course Information

Prerequisites

CSL2020 and CSL2040 or working knowledge of Algorithms and Discrete Mathematics.

Books

1. Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.

Evaluations

1. 20% - Project (a presentation on a paper/topic in groups of two)
2. 20% - Best 2 out of 3 quizzes (Mostly MCQs and T/F)
3. 30% - Two minors (15% each).
4. 30% - Major.
5.  0% - Problem sets with solutions or solution links

Office Hours

Mail me to fix an appointment

Lectures

1. Course overview ( Slides )
2. Formalising Problems ( Slides )
3. Formalising the Computational Model: Turing Machines ( Slides )
4. Examples of TMs and Computers vs Turing machines ( Slides )
5. Variants of Turing Machines ( Slides )
6. Universal Turing Machine ( Slides )
7. Halting Problem, Reductions, Complexity Class P ( Slides )
8. Complexity Class NP, P vs NP, Nondeterministic TMs ( Slides )
9. NP via NTMs, NP-Completeness and NP-Hardness ( Slides )
10. Cook-Levin Theorem ( Slides )
11. Cook-Levin Theorem (contd.), Search vs Decision ( Slides )
12. Some more NP-complete problems ( Slides )
13. coNP and NP vs EXP ( Slides )
14. Space-bounded Computation, L, NL, PSPACE, NPSPACE ( Slides )
15. Savitch's Theorem, NL-completeness ( Slides )
16. NL-completeness (contd.), verifier NL ( Slides )
17. NL = coNL ( Slides )
18. PSPACE-completeness ( Slides )
19. PSPACE-completeness (contd.) ( Slides )
20. Hierarchy Theorems ( Slides )
21. Ladner's Theorem ( Slides )
22. Ladner's Theorem (cont) ( Slides )
23. Oracle TMs and Limits of Diagonalization ( Slides )
24. Baker Gill Solovay's Theorem ( Slides )
25. Polynomial Hierarchy ( Slides )
26. Complete Problems for Hierarchy Classes and Alternating TMs ( Slides )
27. Time-Space Lower-Bound for SAT ( Slides )
28. Introduction to Boolean Circuits ( Slides )
29. Uniform Circuits, TMs with Advice, Karp-Lipton Theorem ( Slides )
30. Meyer's Theorem, Circuit Lower Bound ( Slides )
31. Non-uniform Hierarchy Theorem, Kannan’s Theorem ( Slides )
32. NC and AC: Subclasses of P/poly ( Slides )
33. P-complete Problems, Branching Program ( Slides )
34. Barrington’s Theorem, Randomized Computation ( Slides )
35. ZPP = RP∩coRP, PIT ( Slides )
36. PM in Bipartite Graphs, Error Reduction ( Slides )
37. Error Reduction, Biased Coins, Adleman’s Theorem ( Slides )
38. Sipser-Gacs Theorem ( Slides )

Problem Sets

1. Problem Set 1
2. Problem Set 2
3. Problem Set 3
4. Problem Set 4
5. Problem Set 5
6. Problem Set 6