Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Lectures: Monday Wednesday 1:25 - 2:40 pm in LSRC D106
Office Hour: Wednesdays 3:00 - 5:00 pm in LSRC D226. Use Piazza for discussions/clarifications.
References:
Most materials in the course can be found in one of the following books.
Randomized
Algorithms, Rajeev Motwani and Prabhakar Raghavan.
Concentration
of measure for the analysis of randomized algorithms by D.
Dubhashi and A. Panconesi.
Probability
and Computing by Michael Mitzenmacher and Eli Upfal.
Topics on matrix algorithms can be found in
Foundations
of Data Science by Avrim Blum, John
Hopcroft and Ravi Kannan.
Prerequisites: Familiarity with algorithms, probability and
linear algebra.
Homework:
Homework 0, due Friday 1/17 at 11:59 pm.
Evaluation:
The course grades will be determined based on:
| Date | Contents | Scribe | References | Future Reading |
| Basic Properties of Random Variables | ||||
| 1/10 | Karger's randomized algorithm for MIN CUT | scribe | Chapter 1.1 | Wiki for the Karger-Stein Algorithm |
| 1/15 | Martin Luther King, Jr. Day. No class | |||
| 1/17 | Linearity of Expectation, MAX 3-SAT, simple recursions | scribe | Chapter 1.4 | Slides by K. Wayne |
| 1/22 | Balls and bins | scribe | Chapter 3.1, 3.6 | |
| 1/24 | Hashing | scribe | Chapter 3.4, 8.4 | Chapter 8.5 |
| 1/29 | Biased Coin, distance of distributions | scribe | Chapter 3.2 Notes by Y. Mansour |
Pollard's Book Chapter |
| Concentration Inequalities | ||||
| 1/31 | Chernoff bounds, Bernstein Inequalities | scribe | Chapter 4.1 | |
| 2/5 | Oblivious Routing | scribe | Chapter 4.2 | Lecture note by Sheideler |
| 2/7 | Power of two choices | scribe | Notes (A.
Gupta) Presentation |
|
| 2/12 | Martingales, Azuma's Inequality, Bounded Difference | scribe | Chapter 4.4 | |
| Dimension Reductions | ||||
| 2/14 | Dimension Reduction, Johnson-Lindenstrauss | scribe | Chapter 2.7 in BHK | |
| 2/19 | Applications of Dimension Reduction: Streaming and Communication models | scribe | Chapter 6.2.4 in BHK |
Chapter 6.1, 6.2 in BHK |
| 2/21 | Locally sensitive hashing | scribe | Notes (A. Andoni and I. Razenshteyn) | Notes on a later lecture (A. Andoni and I. Razenshteyn) |
| 2/26 | Graph Sparsification I: Spectrum of graph, effective resistance | scribe | Chapter 6.4 | Lectures (especially lecture 1) by Nikhil Srivastava |
| 2/28 | Graph Sparsification II: matrix concentrations | scribe | ||
| 3/5 | Randomized Algorithms for matrices, SVD and CUR decomposition | scribe | Chapter 6.3 in BHK | |
| 3/7 | Sparse subspace embeddings | scribe | Chapter 2.1 of David Woodruff's Survey | |
| 3/12,3/14 | Spring recess, no class | |||
| Markov Chains | ||||
| 3/19 | Random walk on graph, stationary distributions | scribe | Chapter 6.2 | Chapter 6.1 Chapter 4.1 in BHK |
| 3/21 | Resistor network revisited. |
scribe | Chapter 6.3 - 6.4 |
Chapter 4.5 in BHK |
| 3/26 | Expanders, fast mixing | scribe | Chapter 6.7 | Luca Trevisan's note |
| 3/28 | Hard side of Cheeger's inequality | scribe | Chapter 6.7 | Shayan Oveis Gharan's note |
| 4/2 | Approximate Counting I: DNF counting | scribe | Chapter 11.1-11.2 | |
| 4/4 | Approximate Counting II: Matchings, MCMC | scribe | Chapter 11.3 | Chapter 11.4 |
| Special Topics | ||||
| 4/9 | Stochastic Optimization | |||
| 4/11 | Near linear time Laplacian solvers | Slide by Lorenzo Orecchia | Paper | |
| 4/16 | Randomized complexity classes, derandomization | Chapter 7.2 (for PIT) | Luca Trevisan's slides | |
| 4/18 | Constructive Lovasz Local Lemma |
scribe | Chapter 5.5 | Lance Fortnow's Blog Post Ronitt Rubinfeld's Lecture Note (with longer but more general proof) |
| Time TBD | Take Home Final | |||