Computer Science Tel-Aviv University

0368.4159 Randomized and Derandomized Algorithms

Spring 2011

Announcements

Next meeting: Wedensday, 22/6/2011, shenkar 104 (usual place).

---

Info

When and where: Mondays 10:00-13:00, Shenkar 104.

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.

Grading: either:

· 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

· Ask me to check your solution.

Problem file - Last updated: after lecture 10.

---

Lecture notes on the web

· Salil Vadhan , Pseudorandomness

· Luca Trevisan, Computational complexity - 2008

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

· 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

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. Saraf, M. 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 Lectures: 8 – RL and random walks Lecture 9 – Cheeger inequality (we skipped the proofs), Lecture 10 – Cheeger is tight (we skipped completely), 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	[RL is contained in SC] 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	E. Rozenman, S. Vadhan Derandomized Derandomized squaring of Graphs.
10. 30/05/2011	Luca Trevisan. Extractors and Pseudorandom Generators J. of the ACM, 48(4):860-879, 2001. Full version [ps] [pdf] [Conference Proceedings]
11. 6/6/2011	V. Kabanets and R. Impagliazzo, Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds .
12. 13/6/2011	List decoding RS codes. Sudan’s Lecture 12 (10/29): 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		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]
		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) 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] Adelman: BPP is in P|poly Karp Lipton: If NP is in P|poly then PH= Σ2 . The same if NP is in BPP. Interpretation: an indication that BPP can not solve SAT
	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 AC^0 The NW generator. [Impagliazzo Wigderson]: If E requires exponential size circuits than BPP=P. "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(log^2n). 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.