Computer Science
Tel-Aviv University

0368.4215
Explicit Constructions of extractors

Fall 2005
Spring 2006

 

#Announcements #Handouts #Some information #Classes so far #Suggested papers

Announcements

[18/5/2006] Two new exercises.

[17/5/2006] Room change. The last class (Wed, 14/6) will be given in Orenstein 102.

[26/4/2006] A new exercise. An initial list of suggested papers.

[16/3/2006] A change in homework policy. You will need to solve half of the exercises I give you and submit it to me. I will do random checks (to get an impression of you). The exercises will not be marked and will not be part of the final grade.

[16/3/2006] Room change. The next two classes (22.3 and 29.3) will be given in Orenstein 110 (our usual room is needed for some other purpose).



Handouts




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

Epsilon-bias and tail bounds

Due date: 14/June/2006

4

Extractors, Generators and space bounded

Due date: 1/July/2006

Some Information

Lectures

Wed 15:00-18:00, Melamed

Instructors

Amnon Ta-Shma | 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

· Dan Spielman

· Michael Luby & Avi Wigderson, Pairwise Independence and Derandomization

· Shlomo Huri

· Noam Nisan, Extracting Randomness: How and Why -- A survey

C

Classes so far

Date

Class Topic

1. March 8

Super-concentrators. A-expanding 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

Pair-wise independence. Finding a large cut in a graph. Deterministic amplification of BPP using pair-wise independence.

Derandomizing classes. Pseudo-random generators. Why do we need to cheat non-uniform adversaries. Branching programs.

5. April 5

A PRG (using expanders) against branching programs (INW style with N style proof). Strong and non-strong structures. A strong construction using pair-wise 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. Pair-wise independence as a strong extractor.

7. May 10

k-wise independence, and a lower bound on the size of the sample space. Linear tests and the Fourier coefficients. Epsilon-bias distributions (one construction from AGHP). Almost k-wise independence.

8. May 17

The SZ extractor. Revisiting the space-bounded 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 pseudo-random 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 min-entropies.

The SU reconstructive generator (may be with a partial proof? Or just the extractor).

12. June 14

The Zig-Zag construction. Beating the D/2 bound. Slightly unbalanced lossless condensers.

 

====================================================================================================

Suggested papers

** 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.

  1. Paterson's version of the AKS sorting network. Karp lecture notes.

  2. Explicit unique-neighbor expanders
    N Alon, M Capalbo - Foundations of Computer Science, 2002.

  3. A. Wigderson, Xiao.

A randomness-efficient sampler for matrix-valued functions and applications
46th Annual Symposium of FOCS 2005, pp. 397-406, 2005.
(Abstract) [ Proceedings version (ps) ] [ Proceedings version (pdf) ] [bibTeX entry]

  1. C-J Lu, O. Reingold, S. Vadhan, A. Wigderson.

Extractors: Optimal up to Constant Factors
35th Annual ACM Symposium, STOC 2003, pgs 602-611, 2003.
(Abstract) [ Proceedings version (postscript) ] [ Proceedings version (pdf) ] [bibTeX entry]

  1. Anup Rao Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
    To appear in STOC 2006. Co-Winner of the Danny Lewin Best Student Paper Award.

abstract