CS 278 -- Computational Complexity -- Spring 2008

[general info]  [lecture notes] [Midterm and Project]

General Information

Lecturer: Luca Trevisan, luca@eecs, 679 Soda Hall, Tel. 642 8006

Classes are Tuesday-Thursday, 2-3:30pm, 405 Soda

Office hours: Wednesdays, 2-3pm, or by appointment

References: the main reference for the course will be lecture notes. New lecture notes will be distributed after each lecture. Meanwhile, you can also refer to older notes

Two very good new textbooks are coming out soon, and preliminary versions are freely available on the web

It is also good to have a copy of

About this course: Computational Complexity theory looks at the computational resources (time, memory, communication, ...) needed to solve computational problems that we care about, and it is especially concerned with the distinction between "tractable" problems, that we can solve with reasonable amount of resources, and "intractable" problems, that are beyond the power of existing, or conceivable, computers. It also looks at the trade-offs and relationships between different "modes" of computation (what if we use randomness, what if we are happy with approximate, rather than exact, solutions, what if we are happy with a program that works only for most possible inputs, rather than being universally correct, and so on). 

This course will roughly be divided into two parts: we will start with "basic" and "classical" material about time, space, P versus NP, polynomial hierarchy and so on, including  moderately modern and advanced material, such as the power of randomized algorithm, the complexity of counting problems, and the average-case complexity of problems. In the second part, we will focus on more research oriented material, to be chosen among: (i)  PCP and hardness of approximation; (ii) lower bounds for proofs and circuits; and (iii) derandomization and average-case complexity.

There are at least two goals to this course. One is to demonstrate the surprising connections between computational problems that can be discovered by thinking abstractly about computations: this includes relations between learning theory and average-case complexity, the Nisan-Wigderson approach to turn intractability results into algorithms, the connection, exploited in PCP theory, between efficiency of proof-checking and complexity of approximation, and so on. The other goal is to use complexity theory as an "excuse" to learn about several tools of broad applicability in computer science. Depending on how far we will go, we will see enough Fourier analysis and learning to know how to learn decision trees with membership queries, enough graph theory to build constant-degree expander graphs from scratch and to have an understanding of why spectral partitioning algorithms work, and enough algorithmic coding theory to know how to decode Reed-Solomon codes.  

For reasons that are only partially understood, a disproportionate number of the most beautiful results in Complexity theory in the 80s and 90s have been found by Berkeley graduate students. Hopefully you will feel upon yourselves the mission of continuing this tradition before the current decade ends.

Classes and Lecture Notes

Note: the homeworks are for your enjoyment only. You don't have to solve them and they are not meant to be turned in.

  1. Lecture 1 (1/22) Introduction, deterministic hierarchy theorem. [notes]
  2. Lecture 2 (1/24) Nondeterministic hierarchy theorem. Boolean circuits. [notes]
  3. Lecture 3 (1/29) Randomized algorithms, Adleman's theorem. [notes
  4. Lecture 4 (1/31) Polynomial hierarchy, BPP in Sigma2. [notes
  5. Lecture 5 (2/  5) Karp-Lipton theorem, Valiant-Vazirani [notes
  6. Lecture 6 (2/  7) Approximate counting [notes

    NO CLASS February 12 and February 14

  7. Lecture   7 (2/19) Space complexity, L, NL, NL-completeness, Savitch's theorem [notes
  8. Lecture   8 (2/21) Undirected connectivity, Randomized Log-space, introduction to eigenvalues and expanders [notes]
  9. Lecture   9 (2/26) Eigenvalues and expanders, continued [notes]
  10. Lecture 10 (2/28) Tight examples for Cheeger's inequality [notes (updated 3/19)]
  11. Lecture 11 (3/  4) Eigenvalues and random walks; the expander mixing lemma [notes]
  12. Lecture 12 (3/  6) The zig-zag graph product and explicit constructions of expanders [notes]
  13. Lecture 13 (3/11) Another analysis of the zig-zag product, and turning any graph into an expander  [notes]
  14. Lecture 14 (3/13) Reingold's connectivity algorithm [notes]

    NO CLASS March 18

  15. Lecture 15 (3/20) Statement of the PCP theorem and hardness of approximation [notes]
    [Practice Midterm]

    SPRING BREAK March 24-28
  16. Lecture 16 (4/   1) Overview of the proof [notes]
    [Midterm out: covers up to Lecture 14]
  17. Lecture 17 (4/   3) Amplification phase [notes]
  18. Lecture 18 (4/   8) Amplification phase, continued  [notes]
  19. Lecture 19 (4/ 10) Amplification phase, conclusion  [notes]
  20. Lecture 20 (4/ 15) Range reduction
  21. Lecture 21 (4/ 17) Range reduction, continued
  22. Lecture 22 (4/ 22) Applications to hardness of approximation
  23. Lecture 23 (4/ 24) Average-case complexity [notes]
  24. Lecture 24 (4/ 29) Average-case complexity
    No class May 1 (Department retreat)
  25. Lecture 25 (5/ 6) Natural Proofs
  26. Lecture 26 (5/ 8) Natural Proofs


Tentative plan: (updated 3/11 4/14)

Lectures 1-6: time complexity
P, NP, randomized algorithms, circuits, polynomial hierarchy, approximate counting

Lectures 7-14: space complexity
expanders, Reingold's algorithm

Lectures 15-22: PCP
Dinur's proof of the PCP theorem and applications to approximability

Lectures 23-24: Hardness of random 3SAT
Levin's theory of average-case complexity; proof complexity  lower bounds

Lectures 25-: Pseudorandomness, Natural Proofs, and Learning
Parity lower bounds, one-way permutations, Goldreich-Levin, PRGs, PRFs, applications to encryption and authentication, Natural Proofs, Goldreich-Levin as a learning algorithm, learning decision trees and AC0 circuits with queries

Midterm and Project

Practice Midterm

Midterm due April 15

Information about projects