**CS 761**

**CS 761: Randomized Algorithms**

This is a graduate course on the use of randomness in computations and combinatorics. We study basic techniques in probabilistic analysis with classical and modern applications in theory of computing.

Lecture: | Tuesdays and Thursdays, 11:00-12:20, DC 2568 |
---|---|

Instructor: | Lap Chi Lau |

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

Piazza page: | piazza.com/uwaterloo.ca/summer2023/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.

- graph algorithms: min-cuts, Steiner cuts, shortest paths.
- probabilistic methods: first moment, second moment, local lemma.
- concentration inequalities, martingales
- geometry: dimension reduction, metric embeddings.
- linear algebra: spectral sparsification, subspace embedding, Laplacian solver.
- random walks, electrical networks.
- Markov chain: Monte Carlo method, mixing, coupling, approximate counting.
- algebraic techniques: parallel matching, network coding, matrix rank.
- 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 2018. |