Course Outline
This is a graduate level elective course that introduces topics in computational
complexity. Computational complexity is a study of the resources necessary and sufficient to solve
a given set of problems.
We will study many classical results in
the first part of the course. In the second part, we will study advanced topics in complexity theory.
The detailed course outline is available here.
[pdf]
Part I
In the first part of the course, we will study the following topics.
Introduction to the course, Turing Machines, Time hierarchy theorem.
P, NP, NP hardness, Cook-Levin theorem.
Space complexity classes - L, NL, PSPACE, NPSPACE, Savitch’s theorem, proof of NL=coNL.
Turing machines with randomization, BPP, examples of problems in BPP, non-uniform circuits.
BPP is contained in P/poly.
coNP is contained in IP and IP = PSPACE.
Part II
In the second part of the course, we will explore one of the following research themes in detail.
Algebraic complexity theory and lower bounds.
Boolean circuit complexity and lower bounds.
Communication complexity and information theory.
PCP theorem and applications.
Assignments and quizzes
I have offered this course several times and I have a big question bank created in collaboration with
Prahladh Harsha , which is available on demand. Please write to me if you need access
to the question bank.