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.	Lecture 1	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.	Lecture 2
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.	Lecture 3
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.	Lecture 4
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.	Lecture 5
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.