Randomized Algorithms (semester 2021A)

Weizmann Institute of Science

[Course description] [Announcements] [Lectures] [Assignments] [Reading material]

Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: n/a

When and where: Monday 14:15-17:00, taught via Zoom ~~Ziskind Lecture Room 1~~

First class: Oct. 26, 2020

FGS code: 20214051

Syllabus: Algorithms that are randomized, i.e., use coin tosses during their execution, are central in many computational scenarios, and have become a key tool in Theoretical Computer Science and in application areas. The course will cover the development and use of such probabilistic techniques, including some of the following topics: Concentration results; Simulating randomness, in particular limited independence; Load balancing; Routing algorithms; Randomized rounding; Sampling and sublinear algorithms; Algorithms in the data stream model; Communication protocols and the sketching model.

Prerequisites: Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level.

Final: There will be a final assignment (take-home exam).
Here is the final exam itself.

Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2021a-RandomizedAlgorithms

Previous offerings:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2019a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2017a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2015a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2013a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2011a-RandomizedAlgorithms

Announcements

2020-12-07: Take-home exam schedule: distributed Feb. 1, due within 1 week
2020-10-19: The "Grade Breakdown" in the FGS course details (the method of determining the grade in the course) has changed and it will be based 100% on a final assignment (take-home exam).

Lectures

2020-10-26, Moni + Robi: Minimum Cut via Randomized Contractions; Random Walks on Graphs.
Class material: slides #1, lecture notes #1a, lecture notes #1b, see also [MR, chapters 1.1 and 6.3] and [MU, chapters 1.4 and 7.4].
2020-11-02: 2-SAT, 3-SAT and Complexity Classes; Cover Time.
Class material: slides #2, lecture notes #2a, lecture notes #2b, see also [MR, chapters 6.1, 6.6, 6.5] and [MU, chapters 7.1. and 7.4].
2020-11-09: Chernoff Bounds, BPP Amplification; Electrical Networks.
Class material: slides #3, lecture notes #3a, lecture notes #3b, see also [MR, chapters 1.5, 7.1 and 6.4], [AS, Appendix A] and [MU, chapters 1.3].
2020-11-16: no class (SIGD)
2020-11-23: Streaming Algorithms, Multiset equality; Effective Resistance.
Class material: slides #4, lecture notes #4a, lecture notes #4b, see also [MR, chapters 6.4].
Further reading: [Levin, Peres, and Wilmer, chapter 9], [Doyle and Snell, also as arXiv:math/0001057], [Lyons and Peres, chapter 2].
Further reading: [Feige, slides on cover time].
2020-11-30: Streaming Algorithms; Dimension Reduction in l_2.
Class material: slides #5, lecture notes #5a, lecture notes #5b.
Further reading: [Rao and Yehudayoff, chapter 6, eBook available inside Weizmann], [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2].
2020-12-07: Streaming Algorithms, K-wise Independence, Card Guessing; Fast JL.
Class material: slides #6, lecture notes #6a, lecture notes #6b.
2020-12-14: How To Guess Cards with Little Memory; Fast JL and the JL Transform.
Class material: slides #7, lecture notes #7a, lecture notes #7b.
2020-12-21: Guess the cards, the Lovasz Local Lemma; Oblivious Subspace Embedding.
Class material: slides #8, lecture notes #8b.
2020-12-28: The Lovasz Local Lemma; in-class exercises on the JL transform.
Class material: slides #9, lecture notes #9a, problem set #1.
2021-01-04: The Algorithmic Lovasz Local Lemma and Cuckoo Hashing; Regression via OSE, Importance Sampling.
Class material: slides #10, lecture notes #10a, lecture notes #10b.
2021-01-11: Cuckoo Hashing; Sparse JL Transform.
Class material: slides #11a, lecture notes #11a, slides#11b.
2021-01-18: Bloom Filter, Derandomization, Cuckoo Hashing; Graph Laplacians and Spectral Sparsification.
Class material: slides #12a, lecture notes #12a, lecture notes #12b.
2021-01-25: Balls and Bins, Two-Choice Paradigm; Spectral Sparsification (cont'd).
Class material: slides #13a, lecture notes #13a, lecture notes #13b.

Assignments

(Should usually be turned in within two weeks)

There will be no requirement to hand-in assignments during the semester. Any exercises/homework will be for self-practice and will not be checked.

Reading material

Relevant textbooks:

[MR] Randomized Algorithms by Motwani and Raghavan (errata) -- eBook available inside Weizmann.
[MU] Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal (errata).
[DP] Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi (errata) -- eBook available inside Weizmann.
[AS] The Probabilistic Method by Alon and Spencer (4th Edition) -- eBook available inside Weizmann (2nd Edition).

Similar courses (many with lecture notes):

Randomized Algorithms by Nicholas Harvey at UBC (2015)
Randomized Algorithms by Sariel Har-Peled at UIUC (2014)
Randomized Algorithms and Probabilistic Analysis by James R. Lee at UW (2016)
Randomized Algorithms by Avrim Blum and Anupam Gupta at CMU (2011)
Randomized Algorithms by David Karger at MIT (2015)

Useful references:

Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46.
Probability and Random Processes (2nd ed.) by Grimmett and Stirzaker.