Randomized Algorithms

CS 761

Site menu:

• Information
• Notes
• Homework
• Project

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.

CS, Waterloo. Picture by Andrew Davidhazy. Web design by Andreas Viklund.