6.841/18.405 - Advanced Complexity Theory - Spring 2022

MIT

Instructor: Ryan Williams, Office 32-G638, Email rrw@mit
Office Hours Wednesday 3:30-4:30pm, and by appointment

TAs:

Time and Place: Tuesdays and Thursdays, 2:30-4:00, 4-270 (or virtual, as needed)
Lectures will be recorded! If you are enrolled, go here to see lecture 1!

Join the piazza for announcements, lecture notes, lecture videos, psets, etc.
Please sign up on piazza to stay updated on the course, and to ask questions about 6.841/18.405!
(If you are enrolled and you still need the piazza code, please just email me. Or, you can watch the video of lecture 1 to see it.)

Description

The original theory of computation initiated by Alan Turing (and his contemporaries) studies what is computable in principle, without regard to physical constraints on computing. In this theory, the only distinguishing characteristic of what is "tractable" to compute (what can be solved) is the difference between the finite and the infinite: algorithms have finite descriptions, "good" algorithms produce answers after finitely many computation steps, "bad" algorithms run for infinitely many steps.

Computational complexity theory studies the impact of limited resources on computation, and gives many new refined answers to the general problem of "what is tractable." For a computational problem we care about solving often, we want to solve it with the minimum necessary resources. What is a resource? Practically anything scarce that a computation could consume: we can measure computation steps/time, memory usage, computation "size" and "depth" (if we consider Boolean logic circuits), energy consumption, communication between processors, number of processors, number of random bits used, number of qubits used, quality of approximate solutions, number of inputs correct(!) ... the list goes on. (Other names for the field could have been "computational resource theory", or "computational measure theory", but "complexity" is darn catchy!) Complexity also studies how we may "trade" one resource for another: if I want to use less memory to solve a problem, how much more time do I need to take?

We will study this general problem of limited resources on a completely abstract, mathematical level. It may look strange that it's even possible to mathematically study things like the "amount of time a program takes" when there are gazillions of programming languages, architectures, and operating system issues that could affect running time at any given moment. Nevertheless, we can get a handle on what is efficiently computable at a high level, by starting with Turing's model and carefully defining what resources means, so they will not be model-dependent. This project began in the 1960s, and is now one of the major new mathematical programs in the 21st century. Complexity is, as Arora and Barak put it, an "infant science" -- the best kind of science to get into!

The main goal for this course is to develop this mathematical theory and demonstrate its power for understanding efficient computation. Along the way, we will learn whatever necessary math is needed to get the job done -- complexity theory often uses interesting math in unexpected ways.

Expected workload for the course:

Prerequisites:

This is a graduate course, but it is open to anyone.
Formally, the prerequisite is 18.404/6.840 (introduction to the theory of computation).
This version of the course will not require that.

You should probably come with knowledge at the level of either 18.404/6.840 or 6.045/18.400 (automata, computability, complexity) or be ready to pick it up as you go. It might help to have also had 6.046/18.410 (algorithms) but that is not necessary.

Textbook:

Most of the course will be topics from Your instructor has his own preferred way of presenting things, so we will also provide lecture notes. For the first few lectures of the course, Sipser also covers some of the topics. Another reference that is awesome for the intuition (but short on the proofs) is Moore and Mertens' The Nature of Computation. It's like bedtime reading for wee complexity theorists.


What we've done so far

(see piazza for lecture notes)

What's coming

This is a rough plan, subject to change. (Namely because the enrollment may change, which will affect the project schedule at the end of the term.)

  1. 2/1    Overview of the subject, part 1: recalling $P$, $NP$, $PSPACE$, $EXP$, etc.
  2. 2/3    Overview of the subject, part 2: lower bounds, tradeoffs, connections
    (Arora & Barak, Chapters 2-3), pset 0 out
  3. 2/8    $coNP$, nondeterministic time hierarchy theorem, Oracle Turing machines
    (A&B, Chapters 2-3)
  4. 2/10    The polynomial hierarchy: $P^{NP}$, $NP^{NP}$, etc., and its properties
    (A&B, Chapter 5), pset 0 due
  5. 2/15    Review of $LOGSPACE$, time-space lower bounds for SAT
    (A&B, Chapter 5), pset 1 out
  6. 2/17    Oracles and the Relativization Barrier: $P$ vs $NP$ and $NTIME(n)$ vs $TS(n^{1.1},O(log n))$
    (A&B, Chapter 3.4)
  7. 2/22 MONDAY SCHEDULE OF CLASSES -- NO CLASS

  8. 2/24    Space Complexity, $L$ vs $NL$, $NL=coNL$
    (A&B, Chapter 5)
  9. 3/1    Boolean circuit complexity, basic properties
    (A&B, Chapter 6), pset 1 due
  10. 3/3    A little more circuit complexity: Karp-Lipton Theorem, Kannan's Theorem
    (A&B, Chapter 6)
  11. 3/8    Randomized Complexity: $BPP$, Polynomial Identity Testing, $BPP \subset P/poly$
    (A&B, Chapter 7)
  12. 3/10    $BPP \subseteq NP^{NP}$, $ZPP$, $RP$, etc.
    (A&B, Chapter 7), pset 2 out
  13. 3/15    $P$ vs $BPP$, CAPP, Pseudorandom generators
    (A&B, Chapter 20)
  14. 3/17    Derandomization: Pseudorandom generators from hard functions
    (A&B, Chapter 19-20)
  15. 3/22 SPRING BREAK -- NO CLASS

    3/24 SPRING BREAK -- NO CLASS

  16. 3/29    Counting Complexity: $PP$, $\#P$
    (A&B, Chapter 17), pset 2 due
  17. 3/31    The Valiant-Vazirani Theorem
    (A&B, Chapter 17) project proposal due
  18. 4/5    Toda's Theorem: $PH \subseteq P^{\#P}$
    (A&B, Chapter 17)
  19. 4/7    Interactive Proofs, Deterministic $IP$ = $NP$, Graph Non-Isomorphism
    (A&B, Chapter 8)
  20. 4/12    Arthur-Merlin (and Merlin-Arthur) Protocols, Interactive Proofs for $\#SAT$
    (A&B, Chapter 8), pset 3 out
  21. 4/14    $IP = PSPACE$, start PCPs
    (A&B, Chapter 11 and 22), project progress report 1 due
  22. 4/19    PCPs and Inapproximability
    (A&B, Chapter 11 and 22),
  23. 4/21    A "Simple" PCP Theorem: $NP \subseteq PCP[\log^2 n, \log^2 n]$
    (A&B, Chapter 11 and 22)
  24. 4/26    Communication Complexity
    (A&B, Chapter 13), project progress report 2 due
  25. 4/28    Quantum Complexity (or Circuit Complexity in Restricted Models)
    (A&B, Chapter 14), pset 3 due
  26. 5/3    Project Presentations
  27. 5/5    Project Presentations
  28. 5/10    Project Presentations
    project final report due