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





Class Topic

Lecture notes


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


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.