# 0368.4159Randomized and Derandomized Algorithms

## Fall 2008

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

• Thursday, 20/3, 10-1 (Kaplun 118)

• Thursday, 27/3, 10-1 (Kaplun 118)

• Friday, 28/3, 10-1 (Kaplun 118)

• Thursday, 3/4, 10-1 (To be announced later)

### 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).

### Handouts

·        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

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

### Lectures

 Date Topic More details 24.1.08 Tail inequalities Markov, Chebyshev, Chernoff. A comparison for X=sum(X_i) with: 1. no constraints, 2. pair-wise independence and 3. full independence 24.1.08 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] 31.1,7.2,14.2    Complexity background 31.1.08 basic notions The world: P,RP,NP,BPP,Σ2,PH,PSPACE Sipser: BPP is in Σ2 Strong amplification and an alternative proof for BPP is in Σ2 (Goldreich and Zuckerman) MA and AM. We can assume perfect completeness. (Goldreich and Zuckerman) MA is in Σ2. AM in Π2. MA is in AM. 7.2.08 BPP seems like not being strong enough for NP Non-uniformity. P|poly. [AB, 7.6] Karp Lipton: If NP is in P|poly then PH= Σ2 . 14.2.08 More connections between the uniformityand non-uniform worlds. . IP, IP=PSPACE (just the statement) PSPACE in P|poly implies PSPACE=MA NEXP in P|poly implies NEXP=MA (without a proof, IKW) Derandomization vs. circuit lower bounds. 14.2.08 Does a derandomization exist for ACIT? 21.2.08 No derandomization before we prove circuit lower bounds Identity testing ( [AB, 7.2], [MR, 7.1-7.3]). Schwartz Zippel lemma . ACIT is in coRP. The permanent. The determinant. A probabilistic, parallel algorithm for the maximum matching problem (in a bipartite graph).. RNC vs. P. Valiant: The permanent is #P-complete (no proof) Kabanets and Impagliazzo: If Identity testing is in P, then either NEXP requires super-polynomial circuits, or Permanent requires super-polynomial algebraic circuits. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. 28.2.08, 6.3.08 Circuit lower bounds suffice for derandomization. So may be Identity testing is not in P? PRG There are PRG against non-uniform circuits with small support. Such PRG imply derandomization. Nisan's generator fooling AC0 "Summary": Lower bounds "iff" derandomization. 13.3.08 How about circuit lower bounds? Natural lower bounds. Natural lower bounds imply no PRG (and OWF). The original paper: Natural proofs. DLOG Dehueristfy? DLOG Elementary thoughts on discrete logarithms, C. Pomerance, Baby step giant step The pollard's-rho algorithm for DLOG and its heuristic analysis. undirected connectivity in RL 13..308 20.3.08 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. Expanders 27.3.08 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. 28.3.08  2.4.08 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. V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.

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

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