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

**Instructors:** Robert
Krauthgamer and Moni Naor

**Grader:** TBA

**When and where:** Monday 14:15-17:00, Ziskind Lecture Room 1
(no zoom/hybrid)

**First class: Nov. 7, 2022 **

**FGS code:** 20234051

**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:** The final assignment will be a take-home exam.

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

** Previous offerings:**

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

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

- [posted 2023-01-31]:
**Take-home exam schedule:**distributed Feb. 27, due within 3 days. The format/instructions will be similar to previous offerings of this course.

- [posted 2023-01-12]: Problem set 2 was corrected (in Q.#2, the absolute value was changed and also the hint was expanded)
- [posted 2023-01-10]: lecture notes #6 was slightly updated to
fix typos.

- 2022-11-07, Moni: Minimum Cut via Randomized Contractions.

Class material: lecture notes #1, see also [MR, chapters 1.1].

- 2022-11-14, Moni: 2-SAT and 3-SAT.

Class material: lecture notes #2,see also [MU, chapter 7].

- 2022-11-21, Moni: Existential Proofs via Probabilistic
Constructions, Large Deviation Bounds and Communication.

Class material: lecture notes #3, see also [AS, appendix A] and [RY].

- 2022-11-28, Robi: Dimension Reduction in l_2, JL and fast JL.

Class material: lecture notes #4.

Further Reading: [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2]. - 2022-12-05, Robi: JL Transform and Oblivious Subspace
Embedding.

Class material: lecture notes #5.

Further Reading: [Woodruff, section 2, also as arXiv:1411.4357].

- 2022-12-12, Robi: Least Squares Regression and Probabilistic
Embedding into Dominating Trees.

Class material: lecture notes #6.

Further Reading: [Fakcharoenphol, Rao, and Talwar]. - 2022-12-19, Moni: Card Guessing, Hat Guessing and the Local
Lemma.

- 2022-12-26, Moni: Card Guessing, Hat Guessing and the Local
Lemma (cont'd).

Class material: lecture notes #8.

- 2023-01-02, Moni: Cuckoo Hashing

- 2023-01-09, Robi: Probabilistic Embedding into Dominating
Trees (cont'd) and Importance Sampling.

Class material: lecture notes #10, see also [MR, chapter 11.2].

- 2023-01-16, Robi: Coresets for Clustering.

Class material: lecture notes #11, see also [Munteanu and Schwiegelshohn, survey on coresets]. - 2023-01-23, Moni: Bloom Filters, Random Graphs, and Limited
Randomness and the Braverman's Result concerning AC0

Class material: lecture notes #12. - 2023-01-30, Robi: Concentration Bounds and Edge-Sparsification
of Hypergraphs

Class material: lecture notes #13, see also [MR, chapter 4.1], [DP, chapter 1.6] - 2023-02-06, Robi: Graph Laplacians and Spectral Sparsification

Class material: lecture notes #14.

- Problem set 1
(posted Dec. 5)

- Problem set 2 (posted Jan. 2)
- Problem set 3 (posted Jan. 31)

- [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).
- [RY] Communication
Complexity and Applications by Rao and Yehudayoff -- eBook
available inside Weizmann.

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