Princeton University

Computer Science 522


News:
· FINAL is now available. · 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.) 
Professor: Boaz Barak  405 CS Building. Email: Phone: 258 (I prefer email)
Graduate Coordinator: Melissa Lawson  310 CS Building  2585387 mml@cs.princeton.edu
Requirements and grading: Submitting and grading weekly homework assignments (50% of grade), take home final exam (50% of final grade).
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 appendix of the book to brush up on this stuff.
FINAL: The final is now available. You may work on it on any 48 hour period of your choice ending before May 21st 10:00am. You should type up your solutions and email it to me by that date. For more detailed instructions see this document.
This is a graduate course in computational complexity, including both "classical" results from the last few decades, and very recent results from the last few years.
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 1000 bit 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:
I plan to include also some topics, including some results from the last couple of years. These include derandomization, expanders and extractors, Reingold's deterministic O(log n)space algorithm for undirected st connectivity and the PCP theorem. 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 and me. 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.
Another upcoming book you might want to look at is Computational Complexity: A Conceptual Perspective by Oded Goldreich.
Some lecture notes of similar courses: Last year's offering 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
Due  Checker(s)  
HO1 (latex source)  Feb 16  David Eisenstat 
HO2 (latex source)  Feb 23  Indraneel Mukherjee 
HO3 (latex source)  Mar 2  Hossein Bateni 
HO4 (latex source)  Mar 9  Rajsekar Manokaran 
HO5 (latex source)  Mar 16  David Steurer 
HO6 (latex source)  Mar 30  David Eisenstat 
HO7 (latex source)  Apr 6  Indraneel Mukherjee 
HO8 (latex source)  Apr 13  Rajsekar Manokaran 
HO9 (latex source)  Apr 27  David Steurer 
HO11 (latex source)  May 4  Hossein Bateni 
February 2007 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 2007 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 2007 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  May 2007 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 
Additional reading: New Yorker article on Alan Turing.
Oded Goldreich's text on computational tasks and models
mathematical background
Surveys on NP: Please read one of the following surveys:
Additional reading: Goldreich's text on the
P, NP and NPcompleteness. 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. See also this survey on
diagonalization by Lance Fortnow.
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:
Expander graphs: See the following excellent
book by Hoory, Linial and Wigderson on expander graphs.
Additional reading: You can find the story of IP=PSPACE in the following
entertaining survey: Email and the Unexpected Power of Interaction by Laci Babai.
. See 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
Additional reading: A great introduction to cryptography is in
the upcoming book of Katz and Lindell.
See Salil Vadhan's Thesis
for some fascinating insights into the class of languages with statistical (i.e., informationtheoretic secure) zero knowledge proofs.
Additional reading: Lectures 11 and
12 from
Trevisan's pseudorandomness course.
Goldreich's text on pseudorandom
generators (relevant materials is until page 22).
Additional reading: Today's lecture was all taken from the paper "Hardcore 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 11/n hardness for exponential circuits. (We'll show how to get functions like that from functions that are worstcase hard next time).
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 to BPP=P: The "XOR Lemma free" approach 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 "blackbox" 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: The result that either BPP=EXP or there's a nontrivial subexponential derandomization of BPP is from this ImpagliazzoWigdersion 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 ImpagliazzoKabanetsWigderson and ImpagliazzoKabanets
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
We follow the proof of the PCP theorem in this paper by Irit Dinur. A variant 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). Fourier analysis, linearity testing, GoldreichLevin / KushilevitzMansour algorithm for learning Fourier coeefficients. Hastad's longcode test. Paper by Kushilevitz and Mansour. See also Trevisan's lecture on GoldreichLevin algorithm.
Additional reading: See the following sources for more advanced related material:
Additional reading: Raz's paper,
Holenstein's paper
Additional reading: excellent survey by Aharonov. lecture notes by Umesh Vazirani