**CS 761**

**CS 761: Randomized Algorithms**

This is an introductory graduate course on the use of randomness
in computations and combinatorics. The aim is to provide a solid background for researchers to use probabilistic tools in computer science, engineering, or mathematics.

Lecture: | Tuesdays and Thursdays, 12:00-1:20, |
---|---|

Instructor: | Lap Chi Lau |

Office hour: | Thursdays, 1:30-2:30, DC 3120 |

TA: | Hong Zhou |

Piazza page: | piazza.com/uwaterloo.ca/spring2018/cs761 |

We will introduce the basic probabilistic tools and probabilistic methods, and apply these techniques in various different settings. The following is a tentative schedule.

- linearity of expectations, tail inequalities.
- graph algorithms: color coding, min-cut, MST, graph sparsification.
- balls and bins, hashing, power of two choices, data streaming algorithms.
- algebraic techniques: parallel matching, network coding, matrix rank.
- probabilistic methods: first moment, second moment, entropy, local lemma.
- random walks, electrical networks.
- Markov chain: Monte Carlo method, mixing, coupling, approximate counting.
- geometry: dimension reduction, metric embeddings.
- linear algebra: spectral sparsification, Laplacian solver.
- derandomization: conditional probability, k-wise independence.
- complexity: interactive proofs, probabilistic checkable proofs.

Reference: | Mitzenmacher and Upfal, Probability and Computing, Cambridge, 2005. |
---|---|

Reference: | Motwani and Raghavan, Randomized Algorithms, Cambridge, 1995. |

Reference: | Alon and Spencer, The Probabilistic Method, Wiley, 2008. |

Notes: | Course notes 2013, Course notes 2011. |