Computational Complexity (2023)

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

Time & Place. Lectures will happen every Tuesday, 10:00-12:30, 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, etc.

For questions about exercises and homework: Jorge Pereira and Henrique Campos Navas.

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. (50%) The weekly homework (2-3 exercises) will be given each week, to turn in the following week.
(50%) A written exam. Alternatively, guided study + a 1.5h presentation on a Computational Complexity topic of your choice.

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
As people digested the observation of BGS, the field turned combinatorial.

  • Combinatorial models: Boolean Circuits and Formulas, simple upper and lower-bounds (§6)
  • The polynomial hierarchy, Sigma_2EXP not in P/poly. NEXP in P/poly?
  • Algorithms and lower-bounds for constant-depth circuits. (§14)
  • Razborov’s Theorem: mP != mNP (§14)
  • Randomized computation: ZPP, RP, BPP, the quest for derandomization (§7).
  • Hardness versus Randomness. (§19, §20)
  • The Natural-Proofs Barrier (§23)
  • (If there is time) Cryptography and Pseudorandomness, PRGs based on factoring (Blum-Micali) (§9).
  • (If there is time) Communication complexity (§13 and beyond)

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.

  • 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

  • Lesson 1 (September 19). The invention of the computer, and basic notions of complexity. Reading Guide & Homework. Homework Solutions.
  • Lesson 2 (September 26). The Time Hierarchy Theorem and the class NP. Homework is same as for week 1. Reading: read Sections 3.1 and 2.1.
  • Lesson 3 (October 03). NP-hardness. Reading Guide & Homework. Exercise Solutions.
  • Lesson 4 (October 10). Non-deterministic Time-Hierarchy Theorem, space-bounded computations, PSPACE. Reading Guide.
  • Lesson 5 (October 17). Savitch’s theorem. Sudoku vs Sokoban. Reading Guide and Homework. Exercise Solutions.
  • Lesson 6 (October 24). L and NL. The relativization barrier.
  • Lesson 7 (October 31). Boolean formulas. Basic bounds.
  • Lesson 8 (November 7). Lower-bounds for Boolean Formulas
  • Lesson 9 (November 14). Boolean circuits – P/poly, NC, SAC, AC, AC[m], TC
  • Lesson 10 (November 21). Hastad’s Switching Lemma. Parity not in AC0
  • Lesson 11 (November 28). Monotone P != NP.
  • Lesson 12 (December 5). Cryptography, One-way functions, and Pseudorandom Generators.