# 0368.4159 Randomized and Derandomized Algorithms

## Spring 2011

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

·         By exam (mandatory for undergraduate students), or,

·         (a more difficult) take-home exam.

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

### 2011 Lectures

Date

Topic

1.

21/12/11

The Kakeya set problem.

Basic lower bound: Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22:1093-1097, 2009. [ bib | .pdf ]

Upper bound: S. SarafM. Sudan. Improved lower bound on the size of Kakeya sets over finite fields. http://arxiv.org/abs/0808.2499

2.

07/03/11

Multiplicities of multi-variate polynomials over finite fields. Mergers

Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In FOCS '09: FOCS, pages 181-190, 2009. [ bib | .pdf ]

3.

14/03/11

L,RL,NL, BPL, STCON and USTCON.

Random walks on undirected graphs via algebraic expansion.

USTCON in RL.

Space complexity: Arora – Barak – Chapter 4.

Expanders: Luca Trevisan,  Computational complexity - 2008

# Lecture 11 – convergence to uniform and mixing lemma

4.

28/03/11

The privacy amplification problem. Extractors.

Pair-wise independence, 2-universal hash functions.

ILL, optimal entropy loss extractors [NZ: Randomness is Linear in Space].

De-randomization vs. Pseudo-randomness.

Cheating uniform classes vs. cheating non-uniform classes.

5.

04/04/11

PRG against BPL (and polynomial width branching programs).

1.    Extending m to 2m.

A.   Using privacy amplification

B.   Using expander mixing lemma

C.   “Strong” “expander mixing lemma” using 2-universal hash functions.

2.    Extending approach A to many blocs [INW: Pseudorandomness for Network Algorithms ]

3.    Extending approach C to many blocks [N: RL is contained in SC]

6.

11/04/11

Cayley graphs. Character of Abelian groups. The spectrum of the hypercube.

The replacement product.

7.

2/05/11

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.

8.

16/05/11

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.

9.

23/05/2011

10.

30/05/2011

Luca Trevisan. Extractors and Pseudorandom Generators  J. of the ACM, 48(4):860-879, 2001.
Full version
[ps]  [Conference Proceedings]

11.

6/6/2011

V. Kabanets and R. Impagliazzo,

12.

13/6/2011

List decoding RS codes. Sudan’s

Local unique decoding RM codes.

13.

22/6/2011

Local list decoding RM codes.

### 2008 Lectures

 Date Topic More details 24.1.08 Tail inequalities 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] A simple parallel algorithm for the maximal independent set problem, Also [MR,12.3] 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) 7.2.08 BPP seems like not being strong enough for NP 14.2.08 More connections between the uniformityand non-uniform worlds. 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 28.2.08, 6.3.08 Circuit lower bounds suffice for derandomization. So may be Identity testing is not in P? 13.3.08 How about circuit lower bounds? DLOG Dehueristfy? DLOG Elementary thoughts on discrete logarithms, C. Pomerance, Baby step giant step 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.