I am teaching a full 26 lecture course on Complexity this semester:
https://elearn.iiit.ac.in/courses/course-v1:IIITH+M20Temp11+Monsoon_2020/about
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.
Introduction \
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 Compleixty \
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
Randomized Algorithms \
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 \
Property Testing Model | Linearity Test by Blum, Luby and Rubinfield
PAC Learning\
hugo
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: