## 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

1. 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"
2. 01/15:Secretly computing an average, k-wise independence, linearity of expectation, quicksort. (Chap. 1)
3. 01/20:probabilistic inequalities, Chernoff bounds, complexity classes. (Chap. 2.3, 3.1-3.4, 4.1)
4. 01/22:A monte-carlo Minimum Cut algorithm. (Chap. 1.1, 10.2)
5. 01/27:Universal and perfect hashing. (Chap. 8.4, 8.5)
6. 01/29:Balls'n'boxes, lower bounds, Spencer's graduation game. (Chap 2.2.2, 3.1, 3.6, 5.1)
7. 02/03:Randomized rounding, probabilistic method. (Chap 4.3, 5.1, 5.2, 5.6)
8. 02/05:Random walks and cover times. (Chap 6.1, 6.3, 6.4, 6.5)
9. 02/10:Resistive networks, existence of expanders. (Chap 5.3, 6.2)
10. 02/12:Amplifying randomness via random walks on expanders. (Chap 6.7, 6.8)
11. 02/17:Expanders, eigenvalues, and rapid mixing. Randomized Clique hardness reduction.
12. 02/19:Expanders&eigenvalues, intro to approx counting | Noga's quick proof. (Chap 11.1)
13. 02/24:Approximating the Permanent, part 1.(Chap 11.3)
14. 02/26:Approximation the Permanent, part 2.
15. 03/05:[Rachel Rue] An approximation scheme for Euclidean TSP. (See Rachel for slides)
16. 03/10:Analysis of local optimization algorithms. From Aldous-Vazirani and Dimitriou-Impagliazzo
17. 03/12:[Goran Konjevod] Explicit construction of expanders. (See Goran for slides)
18. 03/17:Intro to number-theoretic algorithms. (Chap 14)
19. 03/19:Randomized algorithms for primality testing.
20. 03/31:[Adam Kalai] Byzantine agreement. (Chap 12.6)
21. 04/02:[Nate Segerlind] PCP and approximability, begin NP in PCP(poly,1). (Chap 7.1, 7.8)
22. 04/07:Finish NP in PCP(poly,1). (Here are some old notes of mine).
23. 04/09:[Ion Stoica] The Choice Coordination Problem. (Chap 12.5)
24. 04/14:[Carl Burch] A randomized linear-time MST algorithm (Chap 10.3)
25. 04/16:[Mike Harkavy] Pseudorandom number generators based on hardness of factoring.
26. 04/21:[Mark Moll] Randomized linear programming algorithms. (Chap 9.10)
27. 04/23:Randomized algorithms for on-line problems. (Chap 13.1, 13.3)
28. 04/28: Quantum computation, Shor's factoring algorithm. Slides available outside Wean 4116.
29. 04/30:[Leemon Baird] Thermal ensembles, quantum cryptography, and a really weird algorithm. Slides available outside Wean 4116.