0368.4159
Randomized algorithms and derandomization
CS dept, TelAviv University, Fall 2015

Ben Lee Volk


The WhiteBox case is from a paper by Ran and Amir: Deterministic
Polynomial Identity Testing in Non Commutative Models But there's a twopage explanation of
this in section 4.5 of the arithmetic circuits survey by Shpilka
and Yehudayoff, which already appears on the
website, so maybe it's better to refer people to there. The BlackBox case is from a paper by Agrawal
et al. Hittingsets for
ROABP and Sum of SetMultilinear circuits The paper is a bit long but we will only be interested in
(a subset of the) things that appear on pages 111. 
Gonen Krak


Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem éù ùí 3 ð÷åãåú, ëàùø àú 2 äð÷åãåú
äøàùåðåú òùéðå áëéúä åáúøâéìéí, àæ ääøöàä úéäéä
áòé÷ø òì äð÷åãä äùìéùéú(ùäéà âí òé÷ø äîàîø) 









Lectures Instructor Open to 
Monday,
10:1013:00, Kaplun 319 Amnon TaShma  Schreiber 127  5364 Undergrad
and grad students. 
Textbooks 
·
[V] Salil
Vadhan : Pseudorandomness ·
[LD]
Laskshmivarahan,
Dhall : Analysis and Design of Parallel Algorithms ·
[SY]
Amir Shpilka,
Amir Yehudayoff
: Arithmetic
Circuits: a survey of recent results and open questions. · [MR] Rajeev Motwani, Prabhakar Raghavan Randomized Algorithms 
Grading policy 
Homework
50%, Paper presentation 50% 
Links

·
L. Lovasz Random
walks on graphs: A Survey ·
M. Luby, A. Wigderson Pairwise Independence and Derandomization Foundation and Trends in
Theoretical Computer Science, vol. 1, no. 4, pp. 237301, 2005. ·
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. 
Date 
Class Topic 
Lercture notes (in Hebrew) 
References and notes 
1. Oct 27 
A
randomized algorithm for Perfect matching (PM). The SchwartzZippel lemma.
Some complexity classes. The PRAM model. NC^k and NC. RNC. Arithmetic
circuits. DET is in SAC^1. 
[S] 2.1,2.2 [LD] 7.2 [MR] 12.4 deals with graphs
(rather than bipartite graphs) and with the problem of finding a matching
(rather than just recognizing its existence) 

2. Nov 3 
PIT in coRP. STCON. USTCON in RL. 

3. Nov 10 
Completing USTCON in RL. 


4.
Nov 17 
Finding a maximal independent set
in NC. Pairwise and Kwise independence.
A construction of a kwise independent space. Derandomizing the small space
maximalIS algorithm. Markov, Chebychev,
chernoff. 


5. Nov 24 
Tail inequalities for kwise
independence. Estimating the second moment with a streaming algorithm. Deterministic amplification:
complete independence, pairwise independendce,
kwise independence, walks on an undirected graphs (to be continued). 

N. Alon, Y. Matias
and M. Szegedy. The space complexity of
Approximating the frequency moments. 
6. Dec 1 
Deterministic amplification of
onesided by walking over an expander. Twosided amplification, the Chernoff bound for expander walks (no proof). Powering, tensoring,
replacement product. 

Alexander
Healy, RandomnessEfficient
Sampling within NC^1 (see section 5). 
7. Dec 8 
Constructing fully explicit
expanders with the zigzag product. 
Entropy Waves, the ZigZag Graph Product, and New ConstantDegree Expanders and Extractors by Omer Reingold, Salil P. Vadhan, and Avi Wigderson 

8. Dec 15 
Undirected connectivity in L. UTS
for consistently labeled graphs. 
Undirected
connectivity in logspace by Omer Reingold 

9. Dec 22 
Dispersers. Definition,
nonexplicit construction and lower bounds. Extractors. Parameters of
nonexplicit and optimal extractors. Deterministic amplification
revisited. The privacy amplification problem. 

10. Dec 29 
Branching programs. PRG for
spacebounded computation. INW: A PRG for RL with log^2n seed length. 
Pseudorandomness for Network Algorithms by R. Impagliazzo, N. Nisan, and A. Wigderson. Randomness is Linear in Space by N. Nisan
and D. Zuckerman. 

11. Jan 5 
Nisan’s
generator. RL in Timespace(poly(n),log^2n). 
RL is contained in SC by N. Nisan. 

12. Jan 12 
RL in Space(log^1.5n) Error correcting codes. A
nonexplicit construction and some lower bounds. 
BPHSPACE⊆DPSACE(S3/2) by Michael Saks and Shiyu Zhou 

13. Feb 4 
1bit strong extractors and error
correcting codes. Designs. Trevisan’s
extractor. 
Extractors
and Pseudorandom Generators by
Luca Trevisan 

14. Feb 11 
NW generator: Hardness ve. Randomness. A PRG for BPP under averagecase
assumptions. 
Hardness vs. Randomness by N.
Nisan and A. Wigderson 

Not this year 
Averagecase vs. worstcase
hardness assumptions. Hardness amplification. Error correcting codes. Local
decoding. Local decoding and hardness amplification. Local decoding RD codes.
Local decoding RM codes. Conditional PRG for BPP under worstcase
assumptions. The reverse direction: Derandomization implies some kind of nonuniform hardness
for a uniform function. 
