Computational Complexity (2024)

The course will offer an graduate-level introduction to the field of Computational Complexity.

Time & Place. Lectures will happen every Monday, 14:30-17:00, in room 6.2.38.

Prerequisites. No prior knowledge of Computational Complexity will be assumed, but the pace will be fast. Past experience with programming, algorithms, and/or proofs will help a lot. Basic combinatorics, probability theory, and knowledge of finite fields will be necessary for the course material: we will not teach it during class, but exercises and reading guides will be given for these topics.

  1. People
  2. Method & Syllabus
  3. Class Summaries, Reading Guides and Homework

People

The course is organized by Bruno Loff, who will teach the main lectures. Contact him for questions about course structure, evaluation, homework, etc.

Method & Syllabus

The course will be organized historically, covering the time since the very beginning of the field, up to the early 2000s.

Classes & Study Materials. There will be 1 weekly 2.5 hour lecture on Tuesday morning. You will be given a reading assignment (which you are expected to do), practice exercises with solutions, and homework exercises.
Evaluation Method. (17/20) Two tests, or an exam, averaged for a maximum grade of 17/20.
(20) Alternatively, the average of the two tests (or the exam grade) is averaged with the grade of a presentation, on a Computational Complexity topic of your choice. Last year, students had much higher grade on the presentations. But it is more work.

The book we will use: Computational Complexity, A Modern Approach, by Sanjeev Aurora and Boaz Barak.

Part 1. Complexity Classes and Diagonalization
Where we will study how the field of computational complexity got started, and how it developed in the first 2/3 decades.

  • The invention of the computer: Turing’s machines and the halting problem. (§1)
  • Computer Programs, Random-Access Machines, Complexity measures. (§1)
  • Hierarchy theorems. (§3)
  • Godel’s lost letter, reductions, the Cook-Levin theorem, and the P versus NP problem. (§2)
  • Space complexity: L vs NL vs P vs PSPACE. (§4)
  • The Relativization barrier of Baker, Gill, and Solovay (BGS). (§3)

Part 2. The combinatorial approach, crypto, and pseudorandomness
As people digested the observation of BGS, the field turned combinatorial.

  • Combinatorial models: Boolean Circuits and Formulas, simple upper and lower-bounds (§6)
  • The Cyberneticists’ Lower bounds on formula size
  • Randomized computation: ZPP, RP, BPP (§7).
  • Cryptography and pseudorandomness, the Goldreich-Levin theorem (§9).
  • Hardness versus Randomness: Nisan, Wigderson, Impagliazzo and friends. (§19, §20)
  • Razborov and Rudich’s Natural-Proofs Barrier (§23)

Part 3. Other topics
These topics are for self study, and should result in student presentations. If time is lacking, some of the above will be moved to student presentations, also.

  • Switching Lemma
  • Razborov’s monotone P != monotone NP
  • Interactive proofs
  • Probabilistically-checkable proofs
  • Hardness of approximation
  • Cryptographic primitives and security
  • Discrepancy
  • Lifting theorems
  • Proof Complexity
  • Fourier analysis of Boolean functions
  • Convex optimization
  • Lattice problems
  • Geometric Complexity Theory
  • Hardness amplification
  • Quantum computing
  • Choose your own topic

Class Summaries, Reading Guides and Homework

See last year’s page to get an idea of what we taught then. The program will likely change in a few places.