Computer
Science

0368.4215

Fall
2005


Topic 
Due date/ Remarks 

0 
Error correcting codes for beginners 
Recommended for those who have not seen error correcting codes before. 
1 
Graphs and eigenvalues 
Due date: 5/April/2006 
2 
Space bounded classes 
Due date: 17/May/2006 
3 
Epsilonbias and tail bounds 
Due date: 14/June/2006 
4 
Extractors, Generators and space bounded 
Due date: 1/July/2006 
Lectures 
Wed 15:0018:00, Melamed 
Instructors 
Amnon TaShma  Schreiber 127  5364 
Open to 
undergraduates and graduate students who have taken the complexity class. Students who have not taken complexity yet, can take the class only with a special approval of the lecturer. 
Grading policy 
Each student will have to present a paper to me. There will also be home assignments, but they are optional (and warmly recommended). 
Lecture notes on the web 
· Nati Linial and Avi Wigderson · Cynthia Dwork and Prahladh Harsha · Michael Luby & Avi Wigderson, Pairwise Independence and Derandomization · Noam Nisan, Extracting Randomness: How and Why  A survey 
Date 
Class Topic 
1. March 8 
Superconcentrators. Aexpanding graphs. Expander codes. 
2. March 15 
Decoding expander codes. Amplifying RP. The hardness of Clique. Three graph problems: no small cuts, the Ramsey problem, the bipartite Ramsey problem. The mixing lemma. 
3. March 22 
Eigenvalue and expansion – Tanner inequality. An algebraic condition for no small cuts. Random walks. Expander rapidly converge to the uniform distribution. A bound on the second eigenvalue. Deterministic amplification by an expander random walk. 
4. March 29 
Pairwise independence. Finding a large cut in a graph. Deterministic amplification of BPP using pairwise independence. Derandomizing classes. Pseudorandom generators. Why do we need to cheat nonuniform adversaries. Branching programs. 
5. April 5 
A PRG (using expanders) against branching programs (INW style with N style proof). Strong and nonstrong structures. A strong construction using pairwise independence, and the [N] PRG. 
6. April 26 
A correctness proof for the Nisan generator. A review of the different kinds of issues we encountered so far: 1. compression? (balanced vs. unbalanced) 2. The property needed from the set (not too large/ not too small/ ...) 3. The property we get (expansion/ right number of edges/ close to uniform/ much entropy/ ...). 4. strongness. Mixing as extraction. Pairwise independence as a strong extractor. 
7. May 10 
kwise independence, and a lower bound on the size of the sample space. Linear tests and the Fourier coefficients. Epsilonbias distributions (one construction from AGHP). Almost kwise independence. 
8. May 17 
The SZ extractor. Revisiting the spacebounded generator. The NZ generator. A PRG implies a uniform function hard for circuits. A PRG against BPP assuming an EXP language hard on average for circuits. 
9. May 24 
Designs. The NW pseudorandom generator. 
10. May 31 
Trevisan extractor. Reconstructive PRG. The advice function is a lossless condenser. 
11. June 7 
The TUZ condenser. Getting an extractor for all minentropies. The SU reconstructive generator (may be with a partial proof? Or just the extractor). 
12. June 14 
The ZigZag construction. Beating the D/2 bound. Slightly unbalanced lossless condensers. 
====================================================================================================
** Note that for some papers you do not need to present the whole paper. Choose the paper that you like, and then we will discuss which part you present.
Paterson's version of the AKS sorting network. Karp lecture notes.
Explicit
uniqueneighbor expanders
N
Alon, M Capalbo  Foundations of Computer Science, 2002.
A. Wigderson, Xiao.
46th
Annual Symposium of FOCS 2005, pp. 397406, 2005.
35th
Annual ACM Symposium, STOC 2003, pgs 602611, 2003.
Anup
Rao Extractors for a Constant Number of Polynomially Small
MinEntropy Independent Sources
To appear in STOC 2006.
CoWinner of the Danny Lewin Best Student Paper Award.