0368.4159 Expanders, Pseudorandomness and Derandomization

CS dept, Tel-Aviv University, Fall 2016

 

Our first meeting is on 28/2/16, 12:00 at Shenkar 204.


 

Syllabus (tentative)

 

The Questions Pool for the assignments is here. You will find instructions within.

 

The Take-home exam is here, and the required statement is here. You will find instructions within.

 


 

 

Lecture Sunday, 12:00-15:00, Shenkar (physics) 204

Instructor Amnon Ta-Shma | Schreiber 127 | 5364

Open for Undergrad and grad students.

Syllabus (tentative)

Grading policy 50% final take-home assignment, the rest is exercises and based on participation in class.

 

Textbooks and links

 

         S. Vadhan: Psuedorandomness

         M. Luby, A. Wigderson: Pairwise Independence and Derandomization

         A. Wigderson: Derandomizing BPP - A survey (lecture notes) (Scribe: Irit Dinur, 2002).

         A. Wigderson: Derandomizing BPP - Lecture notes of a Hebrew University course) (Scribe: Ronen Shaltiel, 1998).

         A. Rao Randomness Extractors for Independent Sources and Applicationss (PhD Thesis)

         I. Dinur, U. Feige: Analytical Methods in Combinatorics and Computer-Science

         R. O'Donnell: Analysis of Boolean Functions

         A. Shpilka, A. Yehudayoff: Arithmetic Circuits: a survey of recent results and open questions.

         R. Motwani, P. Raghavan: Randomized Algorithms

         L. Lovasz: Random walks on graphs: A Survey

         The complexity zoo

 

 

 

Date

Class Topic

Lecture notes

References

Feb. 28

Collective coin-flipping and non-oblivious sources, oblivious sources, expanders, the Kamp-Zuckerman extractor against oblivious sources (started).

Lecture 1

March 6

Algebraic expansion, the Kamp-Zuckerman extractor (cont.), two-source extractors, Ramsey graphs.

Deterministic extractors for bit-fixing sources and exposure-resilient cryptography

March 13

The Chor-Goldreich two-source extractor, deterministic amplification with limited independence, deterministic amplification with expanders (started).

Lecture 2

 

March 20

Deterministic amplification with expanders (cont.), seeded-dispersers, seeded-expanders, deterministic amplification with seeded-dispersers.

 

March 27

Fourier analysis on finite Abelian groups and on the Boolean cube. Epsilon-biased sample spaces.

Lecture 3

 

April 3

The connection between epsilon-biased and the Fourier transform, the connection between epsilon-biased and error-correcting codes, almost k-wise independence.

 

April 10

The Fourier transform over {-1,1}, AC0 circuits have approximating polynomials of poly-logarithmic degree, Parity has no small-degree approximation.

Lecture 4

 

May 1

Several notions of approximation, Braverman's theorem that polylog-wise independence fools AC0 circuits.

 

May 8

List-decodable codes, the connection between list-decodable codes and strong extractors outputting one bit. Trevisan's extractor (started).

Lecture 5

 

May 15

Nisan's PRG against AC0 circuits and the NW generator, Trevisan's extractor (finished), reconstructive extractors.

 

May 22

Problems in constructing a 1-source extractors by the table approach, resilient functions for almost independence with bad players, non-malleable extractors, the Chattopadhyay-Zuckerman 2-source extractor (started).

Lecture 6
DRAFT ONLY

 

May 29

The Chattopadhyay-Zuckerman 2-source extractor, Constructing non-malleable extractors (started).

 

 

June 19

Alternating extraction, LR-histories, Independent-preserving mergers, Correlation breakers with advice, Non-malleable extractors.