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?

Staff

Instructor:  Nikhil Balaji (nbalaji)

Slot:  AB (Mon, Thu - 15:30 - 17:00)

Venue: LH 313.4

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, MTL342, MTL783 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)

Credit: Quizzes -- 30% (held every class, best 15 out of X), Peer Review (of Quizzes) - 10%, Minor - 25%, Major  -- 30%, Class Participation -- 5%

Audit: B- grade over all the evaluations required for audit pass.

Schedule

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.