CS 278 -- Computational Complexity -- Fall 2004

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

The [midterm solutions]

General Information


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

Classes are Monday-Wednesday, 10:30-12noon, 320 Soda

Office hours: Mondays, 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

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, the average-case complexity of problems, and interactive protocols. In the second part, we will focus on more research oriented material, to be chosen among PCP and hardness of approximation; circuit, proof complexity, and communication lower bounds; and derandomization, average-case complexity and extractors. 

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. After taking this course, you will hopefully feel upon you the mission of continuing this tradition into the new decade.

Classes and Lecture Notes

  1. Lecture 1 (8/30) Introduction  [notes]
  2. Lecture 2 (9/1) P and NP, hierarchy theorems. (same notes as lecture 1)

    9/6 No class (Labor day)
  3. Lecture 3 (9/8) More on P, NP and hierarchy theorems (same notes as lecture 1)
  4. Lecture 4 (9/13) Space bounded computations  [notes - revised 10/6] 
  5. Lecture 5 (9/15) NL-completeness, Savitch's theorem, NL=coNL (same notes as last lecture)
  6. Lecture 6 (9/20) Non-uniform computations [notes]
  7. Lecture 7 (9/22) Polynomial hierarchy, Karp-Lipton theorem [notes]
  8. Lecture 8 (9/27) Probabilistic algorithms [notes]
  9. Lecture 9 (9/29)  Valiant-Vazirani (same notes as last lecture)
  10. Lecture 10 (10/4) #P and approximate counting [notes]
  11. Lecture 11 (10/6) #P and approximate counting (same notes as last lecture)
    (see these notes on probability if you had difficulty following today's proofs) 
  12. Lecture 12 (10/11) One-way permutations and pseudorandom generators [notes - revised 11/30]
  13. Lecture 13 (10/13) more on one-way permutations and pseudorandom generators (same notes as last lecture) 

    14. 10/18 and 10/20 No class (FOCS)
    this is a good time to start thinking about the final project

  14. Lecture 14 (10/25) Goldreich-Levin [notes]
  15. Lecture 15 (10/27) Learning decision trees (see this very well written paper)  [notes]
      midterm to be posted on 10/31, due 11/8
  16. Lecture 16 (11/1)   More on learning decision trees (same notes as last lecture)
  17. Lecture 17 (11/3)   Pseudorandom functions and Razborov Rudich (notes in preparation)
  18. Lecture 18 (11/8)   More on pseudorandom functions and Razborov Rudich (notes in preparation)
  19. Lecture 19 (11/10) Levin's theory of average-case complexity  [notes]
  20. Lecture 20 (11/15) More on Levin's theory of average-case complexity
  21. Lecture 21 (11/17)  Even more on Levin's theory of average-case complexity
  22. Lecture 22 (11/22)  Reingold's theorem  [notes]
  23. Lecture 23 (11/24)  Reingold's theorem, continued  [notes]
  24. Lecture 24 (11/29) Reingold's theorem, end
  25. Lecture 25 (12/1)  Parity is not in AC0: proof with polynomials  [notes]
  26. Lecture 26 (12/6) Parity is not in AC0: proof with the switching lemma [notes]
  27. Lecture 27 (12/8) Applications of parity lower bounds to learning [notes]

Midterm and Project

Solutions to homeworks for the first 14 lectures

Midterm and Midterm Solutions

Information about the final project (accessible only from within the berkeley.edu domain)

Site Metersince 8/30/04