## 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.
Assignments and grades are posted via Sakai.

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 LemmaPerfect matchings via Gaussian elimination Notes (A. Saberi) MR 12.4 7 Jan. 31 Part 2: Concentration of MeasureMarkov 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):
1. 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.
2. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments, JCSS 58 (1): 137–147, 1999.
3. Practical Hashing Schemes
4. Linear program rounding:
5. Random graphs and power laws:
6. Fan Chung. Four proofs for the Cheeger inequality and graph partition algorithms ICCM 2007
7. Dan Spielman. Expander graphs, Error correcting codes, and Expander codes (course notes)
8. Smoothed analysis or "Why is knapsack easy in practice"?
9. SAT Solvers and Thresholds, or "Why is SAT easy in practice"?