15-852 RANDOMIZED ALGORITHMS
- Instructor: Avrim Blum
- Time: MW 10:30-11:50
- Place: Wean 4615A
- 12 Units, 1 CU
Course description:
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
areas. 
Text:
Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan,
plus papers and notes for topics not in the book.
Office hours: Friday 10:30-12:00
Handouts
- General Course Information
- Homework 1. Due Jan 29.
- Homework 2. Due Feb 10.
Note: If you want, feel free to make changes to the algorithm in problem 5, if it helps you in proving your bounds.
- Homework 3. Due March 5.
- Homework 4. Due March 19.
- Homework 5. Due April 9.
- Homework 6. Due April 30.
Correction: it's ok (esp if you're using the Arora-Karger-Karpinski paper)
to have a running time of the form n^(poly(1/epsilon)).
- Other papers: [Alon], [Gabber-Galil], [LPS], [Jerrum-Sinclair].
Lecture Notes
- 01/13:Admin, Intro, Example: partitioning a
3-colorable graph. "If you can't walk
in the right direction, sometimes it's enough to walk randomly"
- 01/15:Secretly computing an average, k-wise
independence, linearity of expectation, quicksort. (Chap. 1)
- 01/20:probabilistic inequalities, Chernoff
bounds, complexity classes. (Chap. 2.3, 3.1-3.4, 4.1)
- 01/22:A monte-carlo Minimum Cut algorithm.
(Chap. 1.1, 10.2)
- 01/27:Universal and perfect hashing.
(Chap. 8.4, 8.5)
- 01/29:Balls'n'boxes, lower bounds, Spencer's graduation game. (Chap 2.2.2, 3.1, 3.6, 5.1)
- 02/03:Randomized rounding, probabilistic method.
(Chap 4.3, 5.1, 5.2, 5.6)
- 02/05:Random walks and cover times.
(Chap 6.1, 6.3, 6.4, 6.5)
- 02/10:Resistive networks, existence of expanders.
(Chap 5.3, 6.2)
- 02/12:Amplifying randomness via random walks on expanders. (Chap 6.7, 6.8)
- 02/17:Expanders, eigenvalues, and rapid mixing. Randomized Clique hardness reduction.
- 02/19:Expanders&eigenvalues, intro to approx counting | Noga's quick proof. (Chap 11.1)
- 02/24:Approximating the Permanent, part 1.(Chap 11.3)
- 02/26:Approximation the Permanent, part 2.
- 03/05:[Rachel Rue] An approximation scheme for Euclidean TSP. (See Rachel for slides)
- 03/10:Analysis of local optimization algorithms.
From Aldous-Vazirani and Dimitriou-Impagliazzo
- 03/12:[Goran Konjevod] Explicit construction of expanders. (See Goran for slides)
- 03/17:Intro to number-theoretic
algorithms. (Chap 14)
- 03/19:Randomized algorithms for primality testing.
- 03/31:[Adam Kalai] Byzantine agreement. (Chap 12.6)
- 04/02:[Nate Segerlind] PCP and approximability, begin NP in PCP(poly,1).
(Chap 7.1, 7.8)
- 04/07:Finish NP in PCP(poly,1). (Here are some old notes of mine).
- 04/09:[Ion Stoica] The Choice Coordination Problem. (Chap 12.5)
- 04/14:[Carl Burch] A randomized linear-time MST algorithm (Chap 10.3)
- 04/16:[Mike Harkavy] Pseudorandom number generators based on hardness of factoring.
- 04/21:[Mark Moll] Randomized
linear programming algorithms. (Chap 9.10)
- 04/23:Randomized algorithms for on-line problems.
(Chap 13.1, 13.3)
- 04/28: Quantum computation, Shor's factoring algorithm. Slides available outside Wean 4116.
- 04/30:[Leemon Baird] Thermal ensembles, quantum cryptography, and a really weird algorithm. Slides available outside Wean 4116.