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

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

- 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).

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

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

- [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).

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

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