0368.4159
Expanders, Pseudorandomness and Derandomization
CS dept, TelAviv University, Fall
2016

Syllabus (tentative)
Lecture Sunday, 12:0015:00, Shenkar (physics) 204 Instructor Amnon TaShma  Schreiber
127  5364 Open
for Undergrad
and grad students. Syllabus (tentative) Grading
policy 50%
final takehome 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 ComputerScience · 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 
Date 
Class Topic 
Lecture notes 
References 
Feb. 28 
Collective
coinflipping and nonoblivious sources, oblivious sources, expanders, the
KampZuckerman extractor against oblivious sources (started). 

March 6 
Algebraic
expansion, the KampZuckerman extractor (cont.), twosource extractors,
Ramsey graphs. 
Deterministic
extractors for bitfixing sources and exposureresilient cryptography 

March 13 
The
ChorGoldreich twosource extractor, deterministic
amplification with limited independence, deterministic amplification with
expanders (started). 


March 20 
Deterministic
amplification with expanders (cont.), seededdispersers, seededexpanders,
deterministic amplification with seededdispersers. 


March 27 
Fourier
analysis on finite Abelian groups and on the
Boolean cube. Epsilonbiased sample spaces. 


April 3 
The
connection between epsilonbiased and the Fourier transform, the connection
between epsilonbiased and errorcorrecting codes, almost kwise
independence. 


April 10 
The
Fourier transform over {1,1}, AC0 circuits have
approximating polynomials of polylogarithmic degree, Parity has no
smalldegree approximation. 


May 1 
Several
notions of approximation, Braverman's theorem that polylogwise independence fools AC0 circuits. 


May 8 
Listdecodable
codes, the connection between listdecodable codes and strong extractors
outputting one bit. Trevisan's extractor (started). 


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


May 22 
Problems
in constructing a 1source extractors by the table approach, resilient
functions for almost independence with bad players, nonmalleable extractors,
the ChattopadhyayZuckerman
2source extractor (started). 
Lecture 6 

May 29 
The
ChattopadhyayZuckerman 2source extractor,
Constructing nonmalleable extractors (started). 


June 19 
Alternating
extraction, LRhistories, Independentpreserving mergers, Correlation
breakers with advice, Nonmalleable extractors. 

