Spring 2016 - COMPSCI 630 - Randomized Algorithms

Randomization is a key technique in many settings, and is becoming more important in both theory and practice. It does not only lead to algorithms with better performance/fast running time, in some settings it also makes impossible things feasible. In this course we will see examples of the power of randomness. This will include basic techniques like linearity of expectation, union bounds and concentration of measure. We will also focus on the applications related to dimension reduction (in different settings) and Markov Chains.

Announcement: 

Homework 3 posted. Due Apr. 15 in class.

Homework 2 posted. Due Apr. 1 in class.

 Homework 1 posted. Due Mar. 11 in class.

Course Information

Instructor
Rong Ge
D226 LSRC
Email: rongge@cs.duke.edu

Lectures: Wednesdays and Fridays 1:25 - 2:40 pm in LSRC D106

Office Hour: Wednesdays 3:00 - 5:00 pm in LSRC D226. Use Piazza for discussions/clarifications.

Textbook: Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan.

Optional Reading Material: 

Concentration of measure for the analysis of randomized algorithms by D. Dubhashi and A. Panconesi.
Probability and Computing by Michael Mitzenmacher and Eli Upfal.
Foundations of Data Science by
John Hopcroft and Ravi Kannan.

Prerequisites: Familiarity with algorithms, probability and linear algebra.

Evaluation:
The course grades will be determined based on:

Course Outline

Date Contents References Future Reading
1/15 Intro: Randomness and Computation Slides
Random Quicksort, Chapter 1.2
Basic Properties of Random Variables
1/20 Linearity of Expectation, MAX 3-SAT, simple recursions Chapter 1.4 Slides by K. Wayne
1/27 Karger's randomized algorithm for MIN CUT Chapter 1.1 Wiki for the Karger-Stein Algorithm
1/29 Balls and bins Chapter 3.1, 3.6
2/3 Hashing Chapter 3.4, 8.4 Chapter 8.5
2/5 Biased Coin, distance of distributions Chapter 3.2
Notes by Y. Mansour
Pollard's Book Chapter
Concentration Inequalities
2/10 Chernoff bounds Chapter 4.1
2/12 Oblivious Routing Chapter 4.2 Lecture note by Sheideler
2/17 Power of two choices Notes (A. Gupta)
Presentation(B. Vocking)
2/19 Martingales, Azuma's Inequality, Bounded Difference Chapter 4.4
Dimension Reductions
2/24 Dimension Reduction, Johnson-Lindenstrauss Chapter 2.9 in Hopcroft Kannan book.
2/26 MAX CUT, Goemans Williamson algorithm MAXCUT PAPER
3/2 Applications of Dimension Reduction: Streaming and Communication models Chapter 7.1.4 in Hopcroft Kannan book.
Chapter 7.4
Chapter 7.1 in Hopcroft Kannan
3/4 Graph Sparsification I: Spectrum of graph, effective resistance Chapter 6.4 Lectures (especially lecture 1) by  Nikhil Srivastava
3/9 Graph Sparsification II: matrix concentrations
3/11 Randomized Algorithms for matrices, SVD and CUR decomposition Chapter 7.2-7.3 in Hopcroft Kannan book.
Markov Chains
3/23 Random walk on graph, stationary distributions Chapter 6.2 Chapter 6.1
Chapter 5.1 in Hopcroft Kannan
3/25 Resistor network revisited.
Chapter 6.3 - 6.4
Chapter 5.2, 5.5 in Hopcroft Kannan
3/30 Expanders, fast mixing  Chapter 6.7 Luca Trevisan's note
4/1Hard side of Cheeger's inequalityChapter 6.7Shayan Oveis Gharan's note
4/6 Approximate Counting I: DNF counting Chapter 11.1-11.2
4/8 Approximate Counting II: Matchings, MCMC Chapter 11.3 Chapter 11.4
Special Topics
4/13 Near linear time Laplacian solvers Slide by Lorenzo Orecchia Paper
4/15 Randomized complexity classes, derandomization Chapter 7.2 (for PIT) Luca Trevisan's slides
4/20 Constructive Lovasz Local Lemma
Chapter 5.5 Lance Fortnow's Blog Post
Ronitt Rubinfeld's Lecture Note
(with longer but more general proof)
4/28-29Take Home Final