Instructor: Kent Quanrud
Lectures: Tuesdays and Thursdays, 3:00 to 4:15 PM, LWSN 1106 (or Zoom)
Office hours: Tuesdays and Thursdays, 4:15 to 4:45 PM, LWSN 1211 (or Zoom)
Lectures and office hours will be held on zoom to start the semester at the following link:
Syllabus, policies, and procedures
David Karger (MIT).
Sariel Har-Peled (UIUC).
Randomness and Computation.
Alistair Sinclair (Berkeley).
Algorithms for Big Data.
Jelani Nelson (Harvard).
Algorithms for Big Data.
Chandra Chekuri (UIUC).
Avrim Blum and Anupam Gupta (CMU).
Ankur Moitra (MIT).
Salil Vadhan (Harvard).
Randomized Algorithms and Probabilistic Analysis.
Greg Valiant (Stanford).
Textbook: Randomized Algorithms, by Motwani and Raghavan
Other recommended texts include Probability and Computing, by Mitzenmacher and Upfal; and The Probabilistic Method, by Alon and Spencer
Midterm and final are both TBD
|8/25||Heavy hitters||8/27||Linear probing|
Notes on basic probability by Chandra Chekuri; Cormode and Muthukrishnan (2005); Notes from Fall '19 randomized algorithms class; Notes by Moses Charikar; Video lecture by Ankur Moitra; Video lecture by Jelani Nelson; Notes by Chandra Chekuri; Notes from Spring '20 algorithms class on universal hashing
|9/1||Distinct elements||9/3||Dimensionality reduction|
|9/8||Locality Sensitive Hashing||9/10||Min cuts and sparsification|
Handwritten notes from class; Indyk, Motwani (1998); Charikar (2004); Har-Peled, Indyk, Motwani (2012); Andoni and Indyk (2008 survey); Slides by Piotr Indyk; Slides by Chandra Chekuri; Notes by Sanjoy Dasgupta; Notes by Ankur Moitra
|9/15||Sparsification||9/17||Flow and MST|
|9/22||Randomized rounding||9/24||Metric tree embeddings|
Video from Spring 2020; Handwritten notes prepared before class; Handwritten notes from class; Notes by Avrim Blum; Notes by Anupam Gupta; Slides by Chandra Chekuri; Original paper by Raghavan and Thompson; Technical report by Raghavan and Thompson
|9/29||LP duality and oblivious routing||10/1||Line embeddings and sparsest cut|
|10/6||Two theorems by Claude Shannon||10/8||Entropy and Coding|
Handwritten notes from class; Shannon (1948); Shannon (1949); Section 15.1 in Alon and Spencer; Notes by Sariel Har-Peled; 1971 article on entropy in Scientific American; Chapter 6 in Guruswami, Rudra, Sudhan; Survey by Radhakrishnan; Chapter 10 in Mitzenmacher and Upfal
|10/13||A linear map of the web||10/15||Electrical networks and random walks|
|10/20||Electrical networks and the graph Laplacian||10/22||The spectral theorem and convergence rates of random walks|
|10/27||Spectral embeddings and sparsest cut||10/29||(De-)randomized connectivity with logarithmic space|
|11/3||Deterministic connectivity (cont'd)||11/5||Derandomization by random walks|
|11/10||Derandomization by random walks (cont'd)||11/12||Verifying proofs with random walks|
|11/17||Verifying proofs with random walks||11/19||Verifying proofs with random walks|
|12/1||Randomly testing boolean functions||12/3||Random graphs|