Computer Science
Tel-Aviv University

Randomized and Derandomized Algorithms

Fall 2008



Here is our planned schedule for the rest of the semester:

The planned class for Friday 21/3 won't take place because it is Purim.


When and where: Thursday 10:00-13:00, Kaplun 118.

Instructor: Amnon Ta-Shma, Schreiber 127

Open to: undergraduates and graduate students who have taken the complexity class.  Students who have not taken complexity yet, need a special approval from the lecturer.



·        There will be a quiz after 4 classes (Must pass. 20% of final grade).

·        In addition each student will have to present a paper (70% of final grade).



·        Exercises are optional. A random sample will be checked and the grade will not be recorded.


·        Exercises are meant to give students a chance to practice and make sure they understand the lectures. 

          You are very welcome to:

·        Choose the problems you would like to solve,

·        Work with others on a problem,

·        Discuss it with me, and

·        Ask me to check your solution.

Problem file - Last updated 14.3.08


Lecture notes on the web

·        Ronen Shaltiel, Topics in Pseudorandomness (Fall 2005-2006)

·        Salil Vadhan, Pseudorandomness

·        David Zuckerman, Pseudorandomness and Combinatorial Constructions

·        Michael. Luby and Avi Wigderson, Pairwise Independence and Derandomization

·        Shlomo Hoory and Nathan Linial and Avi Wigderson, Expander Graphs and their applications






More details


Tail inequalities


A comparison for X=sum(X_i) with: 1. no constraints, 2. pair-wise independence and 3. full independence



Pair-wise independence.


  • Finding a cut with a least half the edges [LW, 3]

  • Existence - using the probabilistic method

  • A sequential deterministic algorithm

  • A parallel deterministic algorithm using pair-wise independence.

  • Efficiently sampling a pair-wise independent distribution.[LW, 2]



Complexity background


basic notions


BPP seems like not being strong enough for NP


More connections between the uniformityand non-uniform worlds.

  • PSPACE in P|poly implies PSPACE=MA

  • NEXP in P|poly implies NEXP=MA (without a proof, IKW)

Derandomization vs. circuit lower bounds.



Does a derandomization exist for ACIT?


No derandomization before we prove circuit lower bounds

28.2.08, 6.3.08

Circuit lower bounds suffice for derandomization.

So may be Identity testing is not in P?


How about circuit lower bounds?






DLOG Elementary thoughts on discrete logarithms, C. Pomerance,

Baby step giant step

  1. The pollard's-rho algorithm for DLOG and its heuristic analysis.

undirected connectivity in RL




USTCON. SL. A probabilistic logspace algorithm solving USTCON using random walks.

λ2 and λ=max{λ2,-λn}. Small λ implies rapid mixing. (HLW, sec 3). The mixing lemma. (HLW, sec 2.4). Small λ implies small diameter. Small λ implies implies edge expansion. (LHS of HLW Thm 4.11, sec 4.5.1).

Edge expansion implies small λ2 (RHS of HLW, Thm 4.11, sec 4.5.2). Any undirected, non-bipartite, connected graph has a somewhat small λ.

SL is in RL.



The zig-zag construction


An explicit constructions of a constant degree graph with constant spectral gap. [AB, 16.4],

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

A deterministic log-space algorithm for undirected connectivity.




Savtich. BPL in DSPACE(log2n).

Omer Reingold, Undirected ST-Connectivity in Log-Space [AB, 16.5],

Finding a path between s and t.

Universal traversal sequences. Short UTS exist. Explicit UTS for π-labelled graphs.

Universal exploration sequences. Explicit UES.





Suggested papers. (Please consult me before you choose a paper).

  1. M. Luby, A simple parallel algorithm for the maximal independent set problem

  2. V. Kabanets, R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds. Section 7 (we did the other direction in class).

  3. a. V. Arvind, J. Kobler, U. Schoning, R. Schuler. If NP has polynomial size circuits then MA=AM.

    b. N. Vinodchandran, A note on the circuit complexity of PP.

  4. J. Y. Cai. S2p ⊆ BPPNP.

  5. V. Kabanets, J. Y. Cai. Circuit minimization problem.

  6. R. Santhanam, Circuit Lower Bounds for Merlin-Arthur Classes: STOC 2007.

  7. Z. Dvir. On the size of Kakeya sets in finite fields. J. of the AMS (to appear)., 2008. [ bib | .pdf ]

  8. S. Aaronson, A. Wigderson, Algebrization: A new barrier in complexity theory. STOC 08 [ Draft of full version (pdf) ] [ Draft of full version (ps) ]

  9. N. Alon and B. Sudakov, Bipartite subgraphs and the smallest eigenvalue (Edge expansion implies small λ2 (RHS of HLW, Thm 4.11, sec 4.5.2)).

  10. The Alon-Boppana lower bound on the second largest eigenvalue. Sec 5.2 of   Shlomo Hoory and Nathan Linial and Avi Wigderson, Expander Graphs and their applications

  11. J. Friedman,  On the Second Eigenvalue and Random Walks in Random d-Regular Graphs .

  12. E. Rozenman and S. Vadhan Derandomized squaring of graphs.

  13. O. Reingold, L. Trevisan and S. Vadhan, Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC 2006.

  14. K.-M. Chung, O. Reingold and S. Vadhan, S-T Connectivity on Digraphs with Known Stationary Distribution, CCC 2007.

  15. R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for Network Algorithms

  16. M. Saks and S. Zhou BPHSPACE⊆DPSACE(S3/2)

  17. D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number (Theory of Computing, 2007)

  18. V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.

  19. S. Miller, R. Venkatesan. Spectral Analysis of Pollard Rho Collisions

  20. Chvatal's lecture notes on the AKS sorting network.