CPS 630: Randomized Algorithms

Instructor: Kamesh Munagala
Spring Semester, 2013

Randomization is a key technique used in a variety of computational settings - in fact, its use is so ubiquitous that it is hard to be a computer scientist without appreciating the power of randomness. Randomization not only has practical applications, but also leads to mathematically elegant proofs. This course will cover a bit of both aspects. We will try to be comprehensive in presenting basic techniques, and will illustrate each technique with some practically motivated examples. These techniques will include linearity of expectation, concentration of measure and martingales, Markov chains and mixing times, distributed algorithms, and online algorithms.

There are many additional applications that I will be unable to cover; you will be required to read and summarize one such application as part of the course project.

CPS 330 or equivalent is a HARD prerequisite. If you have never studied algorithms before, you have to take CPS 330 instead of this course.
Discussions will be conducted via Piazza. Please post questions/doubts/comments there, and answer questions posted by your classmates.
Assignments and grades are posted via Sakai.

Administration:

Lectures:

Tue/Thu 1:25-2:40 (D106 LSRC)

Office Hours:

(Kamesh) Thu 3-5pm (D205 LSRC)

(Salman) Wed 11-12am (N303A North)

Grading: Homeworks (25%), Paper reading/Course project (25%; see below), MidTerm (25%), Final Exam (25%).

Course Textbooks:
[MR]    Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan. (required)
[DP]      Concentration of measure for the analysis of randomized algorithms by D. Dubhashi and A. Panconesi.
[MU]    Probability and Computing by Michael Mitzenmacher and Eli Upfal

Some nice slides for the material in the [MU] book.
Randomized Algorithms course at CMU
Lecture notes by J. Aspnes (Yale)

Lecture	Date	Topics	Reading List	Self-Study
1	Jan. 10	Part 1: The Beauty of Randomization Introduction to random variables Linearity of Expectation and Max 3-SAT	MR 1.0 MU 2.1-2.5, 1.4 Slides (K. Wayne)	Quicksort MR 1.0 MU 2.5
2	Jan. 15	Randomized Complexity Classes	MR 1.5 Notes (L. Trevisan)
3	Jan 17	Karger's global mincut algorithm Improved MinCut algorithm by recursion	Wikipedia
4	Jan 22	Polynomial identity checking Testing Bipartite perfect matchings	MR 7.1, 7.4 Notes (A. Saberi)
5	Jan. 24	Fingerprinting and Hashing	MR 7.1, 7.4
6	Jan. 29	Isolation Lemma Perfect matchings via Gaussian elimination	Notes (A. Saberi) MR 12.4
7	Jan. 31	Part 2: Concentration of Measure Markov and Chebychev Inequalities Randomized Median Finding	MR 3.1-3.3 MU 3.1-3.4	Coupon Collectors MR 3.6
8	Feb. 5	Chernoff Bounds: Derivation and simplification Applications to discrepancy minimization	MR 4.1, MU 4.2
9	Feb. 7	Sampling and Estimation Techniques Median of means, Importance sampling Approximate counting of combinatorial objects	MR 11.1, 11.2
10	Feb. 12	Oblivious Routing	MR 4.2, MU 4.5.1	Lovasz Local Lemma (MR 5.5) Notes (A. Srinivasan)
11	Feb. 14	Randomized rounding and congestion	MR 4.3
12	Feb. 19	Goemans-Williamson MaxCUT algorithm	MAXCUT Paper
13	Feb. 21	Locality Sensitive Hashing	SimHash paper
14	Feb. 26	Tail bounds for occupancy problems Power of two choices	MR 3.1, 3.6, 4.4.4 Notes (A. Gupta) Presentation (B. Vocking)	Cuckoo Hashing (Notes)
15	Feb. 28	Martingales: Stopping theorem, Wald's identity Application to Actuarial Science: Lundberg's inequality	MR 4.4 MU 12.1-12.3
16	Mar. 5	Azuma-Hoeffding inequality Balls and Bins; Chromatic number	MU 12, MR 4.4
17	Mar. 7	Average case analysis: Euclidean TSP and Karp's Heuristic Tour lengths in Euclidean TSP	Notes Notes Notes (A. Gupta)
		SPRING BREAK
18	Mar. 19	Part 3: Markov Chains and Monte Carlo Randomized algorithm for 3-SAT	MU 7
19	Mar. 21	Stationary distributions Random walks on graphs	MU 7
20	Mar. 26	M/M/1 queue Metropolis algorithm	MU 8.6 MU 10.4
21	Mar. 28	Coupling and Mixing times Uniform sampling of independent sets	MU 11
22	Apr. 2	<< SLACK >>
23	Apr. 4	Part 4: Miscellaneous Luby's maximal independent set algorithm	MR 12.3	How it's done in nature
24	Apr. 9	Weighted majority algorithm	Notes
25	Apr. 11	Yao's min-max principle and lower bounds Zero-sum games	Notes
26	Apr. 16	Take Home FINAL

Paper Reading: I will unfortunately have to skip many interesting topics. However, you will be required to read one or more papers on such a topic, and summarize the ideas in your own words in a few pages. Here are some suggested topics and papers (please let me know if you need more suggestions):

E. J. Candès. The restricted isometry property and its implications for compressed sensing. Compte Rendus de l'Academie des Sciences, Paris, Serie I, 346 589-592.
N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments, JCSS 58 (1): 137–147, 1999.
Practical Hashing Schemes

A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey.
Universal Hashing due to Carter and Wegman

Linear program rounding:

P. Raghavan and C. D. Thompson. (1985) Randomized rounding: A technique for provably good algorithms and algorithmic proofs
M. Charikar (2002). Similarity estimation techniques from rounding algorithms

Random graphs and power laws:

P. Erdos and A. Renyi. (1958) On random graphs I Publicationes Mathematicae 6: 290–297.
P. Erdos and A. Renyi (1960) The evolution of random graphs Pub. Math Inst Hung Acad Sci 5: 17–61.
R. Albert and A. L. Barabasi. Statistical mechanics of complex networks. Reviews of modern physics, 2002.
M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models of the web graph. STOC 2000

Fan Chung. Four proofs for the Cheeger inequality and graph partition algorithms ICCM 2007
Dan Spielman. Expander graphs, Error correcting codes, and Expander codes (course notes)
Smoothed analysis or "Why is knapsack easy in practice"?

R. Beier and B. Vocking. Typical Properties of Winners and Losers in Discrete Optimization. SIAM Journal on Computing, 35(4), 855–881, 2006.

SAT Solvers and Thresholds, or "Why is SAT easy in practice"?

M. Mezard, G. Parisi, and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297, 812-815, 2002.
B. Selman, H. Kautz, and B. Cohen. (1995) Local Search Strategies for Satisfiability Testing
V. Chvatal and B. Reed. Mick gets some (the odds are on his side). FOCS 1992
D. Achlioptas and C. Moore. The Asymptotic Order of the Random k-SAT Threshold. FOCS 2002