Complexity theory studies what problems can and cannot be solved by computers given limited running time and memory resources.
Students are expected to read the corresponding chapter from the textbook (mentioned under readings), before attending the lecture. The lecture is mainly for clearing doubts and covering the most confusing parts.
The is a short course with 13 lectures for students who might not have taken a Theory of Computation course. However sufficient knowledge of discrete maths and algorithms is assumed. It is not supposed to be a rigorous one, for research student, but rather an introduction to field of complexity theory.
Short notes are available with additional references : Consolidated Notes HTML.
Decision Problems | Turing Machines | Efficient Algorithms
Paradox’s, Diagonalization, Undecidablility
Russell’s Paradox and Diagonalization | Universal Turing Machines | Halting Problem
Nondeterminism, NP and Search Problems
Non Deterministic Turing Machines | Nondeterministic Polynomial Time : NP | NP : Verifier Definition | Descision vs Search Problems
Reductions, NP-Completenesss & Cooks Theorem
Polynomial Time Reductions | Cook-Levin Theorem | NP Compeleness / Hardness
More Time Complexity
NP-completeness of Vertex Cover and Subset Sum | EXP and Time Heirachy Theorem | coNP and Map of Complexity classes
Space Complexity classes and some Relationships | Non Determinism and Space : NL-complete, Savith’s Theorem | Overview of next part of course
NL = coNL, Randomization
Recapping Nondeterminism | Immerman-Szelepcsenyi Theorem : NL = coNL | Randomized TMs and Complexity Classes
BPP and Amplification | Approx MAX-CUT | Undirected REACHABILITY in RL
Random Walks, Derandomization and Polynomial Identity Testing
Analysis of Random Walks | Derandomizing MaxCUT | Randomization: PIT and Schwartz-Zippel Lemma
Streaming Algorithms and Lowerbounds
Schwartz Zippel Lemma Proof | Lowerbound for Bracket Matching | Randomized Streaming Algorithm for Bracket Matching
Property Testing Model | Linearity Test by Blum, Luby and Rubinfield
This part of the course will have a total of 50 marks + 5 bonus marks.
2-3 question will be given out at the end of every lecture. There will be one tutorial session per week (to be scheduled), where the assignments for the previous week will be collected, and solutions will be discussed.
Textbook : Computational Complexity by Christos Papadimitriou
Some courses offered elsewhere: