Princeton University
Computer Science Department

Computer Science 522
Computational Complexity

Boaz Barak

Spring 2006

· FINAL is on-line - due May 15th
· All students taking this course should join the mailing list. It's also recommended for anyone planning to go to some of the lectures. (I'll announce in advance on the mailing list the topics for each of the more advanced lectures.)

Latest Lecture | Homework | Admin | Course Info | Reading | Lecture notes

Administrative Information

Lectures: Monday, Friday 3:00-4:20pm, Room: Friend 109

Professor: Boaz Barak - 405 CS Building. Email: Phone: 258- (I prefer email)

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387

Grading: 50% homework (expected 5-6 assignments), 50% take-home final.

Prerequisites: There are no formal prerequisites, but I will assume some degree of mathematical maturity and familiarity with basic notions such as functions, sets, graphs, O notations, and probability on finite sample spaces. See the following assumed knowledge document to brush up on this stuff.

Course Information

This is a graduate course in computational complexity, including both "classical" results from the last few decades, and very recent results from the last year.

Complexity theory deals with the power of efficient computation. While in the last century logicians and computer scientists developed a pretty good understanding of the power of finite time algorithms (where finite can be an algorithm that on on a 1K input will take longer to run than the lifetime of the sun) our understanding of efficient algorithms is quite poor. Thus, complexity theory contains more questions, and relationships between questions, than actual answers. Nevertheless, we will learn about some fascinating insights, connections, and even few answers, that emerged from complexity theory research.

Among the questions we will tackle (for various types of computational problems) are:

For a more technical description, see the description from the course catalog. I plan to include also some topics, including some results from the last couple of years, that were not taught in the last iteration of the course. These include zig-zag construction of expander graphs, Reingold's deterministic O(log n)-space algorithm for undirected s-t connectivity, full proof of PCP theorem (following Dinur's approach). A general recurring theme in this course will be the notion of obtaining combinatorial objects with random and pseudorandom properties.

Perhaps the question that will occur to you after attending this course is "How is it that all these seemingly intelligent people have been working on this for several decades and have not managed to prove even some ridiculously obvious conjectures?". The answer is that we need your help to solve some of these problems, and get rid of this embarrassing situation.


Our main textbook will be the upcoming book Computational Complexity: A Modern Approach by Sanjeev Arora. Drafts of the book will be available from Pequod Copy. Whenever presenting material that is not in this book, I will provide references to the relevant research papers or other lecture notes.

Some lecture notes of similar courses: Sanjeev Arora, Rudich and Blum, Madhu Sudan, Luca Trevisan, Russel Impagliazzo (2), Chris Umans, Oded Goldreich (see also his texts on computational complexity) Feige & Raz, Moni Naor, Valentine Kabanets, Muli Safra (2),

Pseudorandomness courses: Salil Vadhan, Luca Trevisan, David Zuckerman, Oded Goldreich, Venkat Guruswami

PCP and hardness of approximation: Uri Feige, Guruswami and Odonnell,

Other courses: Sanjeev Arora: theorist's toolkit, Madhu Sudan: essential coding theory, Linial and Wigderson: expander graphs


Homework will be given on Monday and are due in the Monday class two weeks after that. You can submit the homework earlier but please do not submit them later. However, I will accept the homework up to one day late at a penalty of 30 points. Each homework assignment will be checked by 1-2 students within a week. The student checking a homework assignment are not exempt from submitting that assignment. The home work grade will be the average of all assignments. I will not drop the lowest graded assignment. However, some assignments will contain more bonus points (i.e., more than 100), and checking homework for the week will give you a 40 point bonus in that assignment (20 if 2 students are checking). I encourage you to use LaTeX to write your solution. You might find the following short guide for LaTeX written by Dave Xiao to be useful (you might also want to look at the source files for the guide: latex-guide.tex and macros.tex). To make typing in LaTeX easier, I will provide the LaTeX source for all the homework exercises available.

Due Checker(s)
LaTeX source
Feb 20 Janet Yoon
LaTeX source
March 6 Mohammad Mahmoody
LaTeX source
March 27 JiMin Song
LaTeX source
April 10 Janek Klawe
LaTeX source
April 24 Nadia Heninger
LaTeX source
--- Rajesh Poddar


You can work on the final in a period of 48 hours of your choice between May 1 to May 15th 1:30pm. The exam needs to be submitted to Mitra Kelly (Room 323) by May 15th 1:30 pm. This is a strict deadline. click here for more instructions.


Lecture Notes and Handouts.

        February 2006 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

                 1    2    3    4  
  5    6    7    8    9   10   11  
 12   13   14   15   16   17   18  
 19   20   21   22   23   24   25  
 26   27   28  
        March 2006 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

                 1    2    3    4  
  5    6    7    8    9   10   11  
 12   13   14   15   16   17   18  
 19   20   21   22   23   24   25  
 26   27   28   29   30   31  
        April 2006 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

  2    3    4    5    6    7    8  
  9   10   11   12   13   14   15  
 16   17   18   19   20   21   22  
 23   24   25   26   27   28   29  
        May 2006 

 Sun  Mon  Tue  Wed  Thu  Fri  Sat

       1    2    3    4    5    6  
  7    8    9   10   11   12   13  
 14   15   16   17   18   19   20  
 21   22   23   24   25   26   27  
 28   29   30   31  

Lecture 1: Monday, February 6, 2006
Introduction, computational model, P, NP

Lecture outline
Handouts: Assumed Background Homework 1 (LaTeX source)
Oded Goldreich's text on computational tasks and models

Reading: Chapter 1. Goldreich's text until page 9 (section 3.2). See also Computational Complexity theory - a teaser by Oded Goldreich.

Additional reading: New Yorker article on Alan Turing.

Lecture 2: Friday, February 10, 2006
NP completeness,CoNP, the Polynomial Hierarchy and P/poly

Lecture outline

Reading: Chapter 2,5,6.

Additional reading: My philosophical musings are not original and largely based on what I believe to be the best survey ever written on complexity: A Personal View of Average Complexity by Russell Impagliazzo. One way to phrase complexity theory's mission is to find out which one of Russell's worlds do we live in.

See Goldreich's text on the P, NP and NP-completeness. You might also want to take a look at this powerpoint presentation on history and importance of NP,NPC etc. by Gilat Kol and Tal Kramer from Moni Naor's course on Key Papers in CS.

More philosophically minded people might also be interested in the following two surveys by Scott Aaronson: Is P vs. NP formally independent and NP complete problems and physical reality.

Lecture 3: Monday, February 13, 2006
Diagonalization, Deterministic and Non-Deterministic Time Hierarchies

Lecture outline

Reading: Chapter 4.

Additional reading: Diagonalization: survery by Lance Fortnow.

Lecture 4: Friday, February 17, 2006
Space Complexity

Definition of PSPACE, L, NL. QBF is PSPACE complete and Savitch's theorem (NSPACE(s) in NSPACE(s^2)). PATH is NL complete. Non-connectivity is in NL (NL=coNL).

Reading: Chapter 4 and emailed handout.

Additional reading:: Goldreich's text on space complexity

Lecture 5: Monday, February 20, 2006
Probabilistic Computation

Definitions of BPP and its friends (RP,ZPP). Error reduction. Some examples: min-cut algorithm, polynomial identity testing. BPP in P/poly. BPP in PH.
LaTeX source

Reading: Chapter 7 and handout.

Additional reading: Goldreich's text on randomized complexity classes. The following books are recommended for a more in depth look at discrete probability and randomized computation:

Lecture 6: Friday, February 24, 2006
Random and pseudorandom walks: undirected st connectivity in RL, eigenvalues, random walks, expanders.

Undirected ST connectivity in RL. Eigenvalues, random walks, and expanders.

Reading: handout on random and pseudorandom walks

Additional reading: See the following excellent notes by Hoory, Linial and Wigderson on expander graphs.

Lecture 7: Monday, February 27, 2006
Random and pseudorandom walks II: error reduction using expanders, graph products, construction of zig-zag expander family.

Improved error reduction for probabilistic algorithms. Construction of the zig-zag expander family.

Additional reading: The zig zag product was defined in this paper by Reingold, Vadhan and Wigderson. However, we're going to use a simple proofs that is taken from the following two papers by Rozenman and Vadhan and Reingold, Trevisan and Vadhan.

Lecture 8: Friday, March 3, 2006
Random and pseudorandom walks III: analysis of zig zag, undirected connectivity in L.

Analysis of the zig-zag product. Undirected ST connectivity in L.

Additional reading: Goldreich's text on UPATH in L contains a good presentation of that algorithm (along with a nice appendix on expanders). In particular, it contains more details on how to implement the algorithm in logarithmic space. The original paper of Reingold can be found here. We note that a very close result (UPATH in space O(log n loglog n)) was obtained simultaneously and independently by Vladimir Trifonov (a grad student in UT Austin) using quite different tools.

Lecture 9: Monday, March 6, 2006
No Lecture: TCC 2006 in New York

Homework: HW3.pdf
LaTeX source

Lecture 10: Friday, March 10, 2006
Counting problems, Toda's theorem.

Counting problems, definition of #P, permanent. Hardness of unique SAT. Toda's theorem.

Lecture 11: Monday, March 13, 2006
End of Toda's theorem proof. Interactive proofs.

Finished proof of Toda's theorem. Definition if interactive proofs. Graph non-isomorphism in IP.

Handout: Counting

Lecture 12: Friday, March 17, 2006
Interactive Proofs, #P in IP

Graph Non-Isomorphism has public coin proof and unlikely to be NP-complete. #P in IP (if there's time we'll show IP=PSPACE).

Handout: Interactive Proofs

Three wonderful surveys for spring break reading (two old and one new):

  • Email and the Unexpected Power of Interaction by Laci Babai
  • The History and Status of the P vs. NP Question by Michael Sipser
  • P, NP and Mathematics - a computational complexity perspective by Avi Wigderson.
  • Additional reading: Goldreich's text on the proof that IP[k] is in AM[k+3]. Goldreich's text on IP=PSPACE. Trevisan's lecture notes on IP=PSPACE

    Lecture 13: Monday, March 27, 2006
    Hardness vs. Randomness 1: Nisan-Wigderson Generator

    Handout: Homework 4 (LaTeX source).

    Additional reading: Lectures 11 and 12 from Trevisan's pseudorandomness course.
    Goldreich's text on pseudorandom generators (relevant materials is until page 22).

    Handout on averaging, hybrid, and prediction vs. distinguishing

    Lecture 14: Friday, March 31, 2006
    Hardness vs. Randomness 2: XOR and Hardcore Lemmas

    Handout: Lecture outline: XOR and hardcore lemmas

    Additional reading: Today's lecture was all taken from the paper "Hard-core distributions for somewhat hard problems" of Russell Impagliazzo (see also his wikipedia entry). The XOR lemma has several different proofs with varying parameters, see this survey by Goldreich, Nisan and Wigderson.

    A derandomized version of the XOR lemma, that given a function on n bits only needs to move to a function on O(n+k) bits to get hardness similar to the hardness the original version's with k repetitions (and hence nk bits) was given in this paper by Impagliazzo and Wigderson. In particular, using what we've seen this paper shows how to get BPP=P from functions with 1-1/n hardness for exponential circuits. (We'll show how to get functions like that from functions that are worst-case hard next time).

    Lecture 15: Monday, April 3, 2006
    Hardness vs. Randomness 3: Using Worst-case assumptions , circuit lower bounds from BPP=P

    Handout:Lecture Outline: Worst-case assumptions

    I highly recommend this survey by Valentine Kabanets on derandomization. It contains brief descriptions and pointers to many of the latest results and exciting research directions of this field.

    Getting BPP=P: The "XOR Lemma free" approach mentioned in the handout to getting BPP=P was given in this paper by Sudan, Trevisan and Vadhan (STV). As mentioned before, there's a previous alternative approach by Impagliazzo and Wigderson using a "XOR Lemma on steroids". There's even a third "NW generator free" approach by Shaltiel and Umans (see below).

    Hardness vs. randomness tradeoff: The results shown in class generalize to a tradeoff between the assumption on the circuit size required to compute functions in E and the resulting time to derandomize BPP. However, the currently known approach to get an optimal tradeoff (by this we mean optimal w.r.t. to "black-box" proofs) is somewhat different (and in particular uses error correcting codes but not the NW generator). This is obtained in the following two papers by Shaltiel and Umans and Umans. You can also see a PowerPoint presentation by Ronen Shaltiel on this topic.

    Uniform derandomization: One fascinating theorem I did not prove is the result that either BPP=EXP or there's a non-trivial subexponential derandomization of BPP. This result is from this Impagliazzo-Wigdersion 98 paper, but a more general and perhaps better proof can be found in this paper by Vadhan and Trevisan. The results that even a uniform derandomization require circuit lower bounds come from these two papers by Impagliazzo-Kabanets-Wigderson and Impagliazzo-Kabanets

    Randomness extractors: Another topic we did not touch is randomness extractors which are used not to derandomize BPP but to execute probabilistic algorithms without access to truly independent and uniform coin tosses. The following survey by Ronen Shaltiel is a good starting point for information on this topic. See also the following presentation by Salil Vadhan.

    More resources on derandomization and pseudorandomness: As you can see, one could make a whole course out of the topics we did not cover on pseudorandomness, and indeed there several such courses with excellent lecture notes were given. Some recommended links are: Shaltiel Trevisan Zuckerman Goldreich Vadhan

    Lecture 16: Friday, April 7, 2006
    PCP theorem 1 : NP in PCP(O(1),poly(n))

    Introduction to PCP and hardness of approximation. NP in PCP with O(1) queries and poly(n) randomness. (Hadamard-based proof for Quadratic equations).
    Guest lecturer: Sanjeev Arora

    Lecture 17: Monday, April 10, 2006
    PCP theorem 2: Outline of proof, alphabet and query reduction steps

    Lecture Outline

    Exercise 5 (Latex Source)

    We follow the proof of the PCP theorem in this paper by Irit Dinur. A veriant of this proof is also described in these lecture notes by Guruswami and Odonnell (these two sources follow a slightly different approach, and we'll also do some things a bit different from both these sources).

    Lecture 18: Friday, April 14, 2006
    PCP theorem 3: Gap amplification, end of proof

    Proof of the gap amplification step (Dinur's lemma).

    We only sketched the two remaining minor steps: reducing to constant degree (each variable appears in constantly many clauses) and reducing from a constant number q of queries to t queries (losing a factor of say 10q in the gap and increasing the alphabet from sigma to sigma^q).

    Lecture 19: Monday, April 17, 2006
    PCP theorem 4: Harmonic analysis and linearity testing.

    Fourier analysis, linearity testing, Goldreich-Levin / Kushilevitz-Mansour algorithm for learning Fourier coeefficients. Hastad's long-code test.

    Handout: lecture outline

    Reading: Chapter 19.6 of the textbook. Paper by Kushilevitz and Mansour. See also Trevisan's lecture on Goldreich-Levin algorithm.

    Additional reading: See the following sources for more advanced related material:

    Lecture 20: Friday, April 21, 2006
    Lowerbounds 1: Clique requires subexponential-sized monotone circuits

    Circuit lowerbounds: draft chapter from book

    Additional reading: I highly recommend looking at the excellent Boppana-Sipser survey on circuit lowerbounds

    Lecture 21: Monday, April 24, 2006
    Lowerbounds 2: AC0 and Hastad switching lemma

    Handouts: lowerbounds chapter Homework 6 (LaTeX source)

    Additional reading: The Boppana-Sipser survey also contains a description of the switching lemma. There's also a survey on the switching lemma by Paul Beame.

    Lecture 22: Friday, April 28, 2006
    Natural Proofs

    Additional reading:the original paper by Razborov and Rudich

    Lecture 23: Monday, May 1, 2006
    Quantum Computation 1, Grover's algorithm

    Additional reading: excellent survey by Aharonov. lecture notes by Umesh Vazirani

    Lecture 24: Friday, May 5, 2006
    Quantum Computation 2, Shor's algorithm