15-859(D) RANDOMIZED ALGORITHMS
Randomness has proven itself to be a useful resource for developing
provably efficient algorithms and protocols. As a result, the study
of randomized algorithms has become a major research topic in recent
years. This course will explore a collection of techniques for
effectively using randomization and for analyzing randomized
algorithms, as well as examples from a variety of settings and problem
- Instructor: Avrim Blum
- Time: TR 10:30-11:50
- Place: Wean 5409B
- 12 Units, 1 CU
Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan,
plus papers and notes for topics not in the book.
Office hours: Monday 10:30-12:00, or by appointment.
Here is the Take-home Final.
Due Friday Dec 11, 4:00pm.
- 09/15:Admin, Intro, Example: partitioning a
3-colorable graph. "If you can't walk
in the right direction, sometimes it's enough to walk randomly"
- 09/17:k-wise independence, linearity of
expectation, quicksort. (Chap. 1)
- 09/22:Randomized complexity classes, a
monte-carlo Min Cut alg. (Chap. 1.1, 1.5, 2.3, 10.2)
- 09/24:Probabilistic inequalities, Chernoff
bounds, begin randomized rounding. (Chap 3.1-3.4, 4.1)
- 09/29:Randomized rounding, probabilistic
method & method of conditional expectations. (Chap 4.3,
- 10/01:MAX-SAT, occupancy problems.
(Chap 5.2, 3.1, 3.6)
- 10/06:Universal and perfect hashing, randomized lower bounds.
Slides for 1st half, Notes for second half. (Chap 8.4, 8.5, 2.2.2)
- 10/08:Random walks and cover times. (Chap
6.1, 6.3, 6.4, 6.5)
- 10/13:Resistive networks, rapid
mixing. (Chap 6.2)
- 10/15:Pseudorandom generators (guest lecture by Steven Rudich.
Notes outside his office).
- 10/20:Expander graphs: random construction, uses,
Impagliazzo-Zuckerman amplification result. (Chap 6.7, 6.8).
- 10/22:Expanders and eigenvalues. Intro to approx
counting. (Chap 11.1)
- 10/27:Approximating the Permanent. (Chap
- 10/29:Number-theoretic algorithms,
intro. (Chap 14)
- 11/03:Randomized algorithms for primality testing.
- 11/05: Analysis of local optimization
algorithms [Bjarni and Adam]
- 11/10: A
randomized linear-time MST algorithm [Mihai and Hal]
(These notes fix some typos in the ones handed out in class)
- 11/12: Lovasz local
inequality, and Talagrand's inequality [Shyjan and Geoff and
Shelby]. Joel Spencer's notes on Talagrand's inequality, and his Ohio State Lectures
(which discuss LLL and Janson's, among other things).
- 11/17: Rounding an SDP [Dan P and Larry and Avrim]. Here are Dan
Pelleg's slides (click on "swap landscape" in ghostview). Here is the
- 11/19: Randomized online algorithms [Gary and Dan T.]. (Chap 13)
- 11/24: Bartal's
Randomized Metric Space Approx and Applications
[Jochen and Erlendur]
- 12/01: Online Machine Learning [Avrim]
- 12/03: Quantum Computing [John and Jesse]