0368.4159 Randomized algorithms and de-randomization

CS dept, Tel-Aviv University, Fall 2015


Our next meeting is on 11/2/15, 10:00 at Schreiber 209.

Out: 28/10/2014, Due: 10/11/2014 Homework 1: Arithmetic and Boolean circuits

Out: 3/11/2014, Due: 17/11/2014 Homework 2: More arithmetic and boolean circuits

Out: 12/11/2014, Due: 24/11/2014 Homework 3: Random walks on graphs

Out: 18/11/2014, Due: 1/12/2014 Homework 4: Pair-wise Independence

Out: 27/11/2014, Due: 8/12/2014 Homework 5: More pair-wise independence and random walks

Out: 2/12/2014, Due: 15/12/2014 Homework 6: Norms, tensors and rotation maps

Out: 10/12/14, Due: 22/12/14 Homework 7: More on expanders

Out: 18/12/14, Due: 29/12/14 Homework 8: Derandomized squaring on directed, regular graphs

Out: 23/12/14, Due: 5/1/15 Homework 9: Extractors

Out: 30/12/14, Due: 12/1/15 Homework 10: PRG for BP

Out: 13/01/15, Due: 2/02/15 Homework 11: ECC, Designs and the Johnson's bound

Out: 13/01/15, Due: 9/02/15 Homework 12: Non-uniform computation

Out: 13/01/15, Due: 9/02/15 Homework 13: Introduction to ECC




Ben Lee Volk




The White-Box case is from a paper by Ran and Amir:


Deterministic Polynomial Identity Testing in Non Commutative Models

But there's a two-page 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 Black-Box case is from a paper by Agrawal et al.


Hitting-sets for ROABP and Sum of Set-Multilinear circuits


The paper is a bit long but we will only be interested in (a subset of the) things that appear on pages 1-11.


Gonen Krak


Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem


3 , 2 , ( )

















Open to


Monday, 10:10-13:00, Kaplun 319

Amnon Ta-Shma | Schreiber 127 | 5364

Undergrad and grad students.




         [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%





The complexity ZOO


         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. 237-301, 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.









Class Topic

Lercture notes (in Hebrew)

References and notes

1. Oct 27

A randomized algorithm for Perfect matching (PM). The Schwartz-Zippel lemma. Some complexity classes. The PRAM model. NC^k and NC. RNC. Arithmetic circuits. DET is in SAC^1.

Lecture 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


3. Nov 10

Completing USTCON in RL.

Lecture 2

4. Nov 17

Finding a maximal independent set in NC.


Pair-wise and K-wise independence. A construction of a k-wise independent space. De-randomizing the small space maximal-IS algorithm.


Markov, Chebychev, chernoff.

Lecture 3


Lecture 3b

5. Nov 24

Tail inequalities for k-wise independence. Estimating the second moment with a streaming algorithm.


Deterministic amplification: complete independence, pair-wise independendce, k-wise independence, walks on an undirected graphs (to be continued).

Lecture 5


Lecture 5b

N. Alon, Y. Matias and M. Szegedy. The space complexity of Approximating the frequency moments.


6. Dec 1

Deterministic amplification of one-sided by walking over an expander.

Two-sided amplification, the Chernoff bound for expander walks (no proof).


Powering, tensoring, replacement product.

Lecture 6


Lecture 6b

Alexander Healy, Randomness-Efficient Sampling within NC^1 (see section 5).

7. Dec 8

Constructing fully explicit expanders with the zig-zag product.

Lecture 7

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors by Omer Reingold, Salil P. Vadhan, and Avi Wigderson

8. Dec 15

Undirected connectivity in L. UTS for consistently labeled graphs.

Lecture 8

Undirected connectivity in log-space by Omer Reingold

9. Dec 22

Dispersers. Definition, non-explicit construction and lower bounds. Extractors. Parameters of non-explicit and optimal extractors.

Deterministic amplification revisited. The privacy amplification problem.

Lecture 9

10. Dec 29

Branching programs. PRG for space-bounded computation. INW: A PRG for RL with log^2n seed length.

Lecture 10

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

Nisans generator. RL in Timespace(poly(n),log^2n).

Lecture 11

RL is contained in SC  by N. Nisan.

12. Jan 12

RL in Space(log^1.5n)


Error correcting codes. A non-explicit construction and some lower bounds.

Lecture 12

BPHSPACEDPSACE(S3/2)  by Michael Saks and Shiyu Zhou

13. Feb 4

1-bit strong extractors and error correcting codes.

Designs. Trevisans extractor.

Lecture 13

Extractors and Pseudorandom Generators by Luca Trevisan

14. Feb 11

NW generator: Hardness ve. Randomness. A PRG for BPP under average-case assumptions.

Lecture 14

Hardness vs. Randomness by N. Nisan and A. Wigderson

Not this year

Average-case vs. worst-case 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 worst-case assumptions.


The reverse direction: Derandomization implies some kind of non-uniform hardness for a uniform function.