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: H (Mon, Wed - 11:00 - 12:00, Thu: 12:00 - 13:00)

Venue: LH 605


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: Problem sets -- 20% (approx), Quizzes -- 30%, Major -- 30%, Project (group activity) -- 20%

Audit: (>50% in the major)


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 (just around the time when the minor is usually held) to read and explore in depth. 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


Week 1

Aug 3,4: No class (since I am traveling). Compensatory classes will be announced soon

Week 2

Aug 8, 10, 11: Intro to the course, context, administrativia, ToC recap: Languages, Machines, Computatation, Undecidability.

Week 3

Aug 15, 18 (holiday), 17, 20: P, NP, coNP: Definitions, Examples, Reductions.

Week 4

Aug 22, 24, 25: NP-completeness, Cook-Levin theorem, 3SAT to Hamiltonian cycle, Subset Sum, Clique.

Week 5

Space Complexity

Week 6

Oracle machines and diagonalization

Week 7

Polynomial Hierarchy and Boolean Circuits

Week 8

Randomized Complexity

Week 9

Interactive Proofs

Week 10

Circuit Lower bounds

Week 11



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.