COL 753 Complexity Theory

Course Description

Computational Complexity theory aims to understand the computational resources (time, memory, communication, etc) needed to solve computational problems, and it is especially concerned with discerning "tractable" problems from "intractable" ones. While the design and analysis of algorithms gives upper bounds on such resources, computational complexity theory is mostly concerned with lower bounds; that is we look for negative results showing that certain problems require a lot of time, memory, etc., to be solved. In particular, we are interested in infeasible problems, that is computational problems that require impossibly large resources to be solved, even on instances of moderate size. It is very hard to show that a particular problem is infeasible, and in fact for a lot of interesting problems, the question of their feasibility is still open. Another major line of work in complexity is in understanding the relations between different computational problems and between different “modes” of computation. A few typical questions we will study are:


  1. Is every problem whose solution is easy to verify also easy to solve?

  2. Does every function implementable with a low memory footprint also have a fast implementation?

  3. Can randomness be used to speed up computations, or the checking of proofs?

  4. If a problem is intractable, can we still solve the problem most of the time, or solve it approximately?

  5. If yes, is it also easy to count how many solutions there are?


Topics

Modeling computation (Finite state machines, Non-determinism, Turing machines, class P etc.), NP and NP-completeness, Diagonalization (Time hierarchy and Ladner's theorem), Space complexity (PSPACE, NL, Savitch's theorem, Immerman-Szelepcsényi theorem etc.), Polynomial hierarchy, Boolean circuits (P/poly), Randomized classes (RP, BPP, ZPP, Adleman's Theorem, Gács-Sipser-Lautemann Theorem), Interactive proofs (Arthur-Merlin, IP = PSPACE), Cryptography (one-way functions, pseudorandom generators, zero knowledge), PCP theorem and Hardness of approximation, Circuit lower bounds (Hastad's switching lemma), Algebraic complexity, Communication Complexity, Other topics (#P, Toda's theorem, Average-case complexity, derandomization, pseudorandom construction)


Prerequisites



COL351, COL352, COL705 OR Equivalent. Essentially, a working knowledge of Discrete Mathematics (Linear Algebra, Combinatorics, Probability) and familiarity with reductions - which is usually covered in a course on Design and Analysis of Algorithms and/or Theory of Computation. If you haven't done the prerequisite courses, but are interested in attending, please send me an email.



Course Logistics and Grading (Tentative)


Problem sets/quizes -- 20% (approx), Mid-sem -- 25% , End-sem -- 35%, Seminar (group activity) -- 20% (approx).


Seminar Topics

Depending on the class strength (the number of students crediting the course), students will be put into groups of size 2 and given topics to read and present. Every group will be expected to give a clear presentation (possibly using electronic presentation) and will be expected to generate an electronic report (preferably using LaTeX).


Schedule

TBD


References

[AB]: Computational Complexity: A Modern Approach - Sanjeev Arora and Boaz Barak

[K]: Theory of Computation - Dexter C. Kozen

[W] Mathematics and Computation - Avi Wigderson

[H] Prahladh Harsha. Computational Complexity, 2011. A course offered at TIFR (Winter/Summer 2011).

[T] Luca Trevisan. CS 278 Computational Complexity, 2002. A course offered at UC, Berkeley (Fall 2002)

[Z] The Complexity Zoo.


Reading/Watching

The P vs NP problem - Clay Math Institute page with article by Stephen Cook.

The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge - Talk at IAS by Avi Wigderson.

Abel Prize 2021 to Laszlo Lovasz and Avi Wigderson.

Randomness vs Pseudorandomness - Talk at IAS by Avi Wigderson.