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

**Instructors:** Robert
Krauthgamer and Moni Naor

**Grader:** Ohad.Trabelsi (at weizmann.ac.il)

**When and where:** Thursday 14:15-17:00, Ziskind Lecture Room
1

**First class: **Nov. 8, 2018

**FGS code:** 20194201

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

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

** Previous offerings:**

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 2019-02-07] the instructions for the final (take-home
exam) will be similar to this 2017
course.

- [posted 2019-01-04]
**Take-home exam**rescheduled: distributed Feb. 25, due within 3 days - [posted 2018-12-28] Take-home schedule: distributed Feb. 10,
due within 3 days

- [posted 2018-12-24] Problem Set 2 was corrected (in Q.#2) with
extended due date

- [posted 2018-11-20] The class of Nov. 29 is moved (room
change) to Wolfson Hall

- 2018-11-08, Moni: (Multi)-Set Equality, Closest Pair, Minimum
Cut.

Reading: lecture notes #1 - 2018-11-15, Robi: Random Walks on Graphs

Reading: lecture notes #2, see also [MR, chapter 6]

Further reading: [Levin, Peres, and Wilmer, chapter 9], [Doyle and Snell, also as arXiv:math/0001057], [Lyons and Peres, chapter 2] - 2018-11-22, Robi: Effective Resistance and an Algorithm for
2SAT

Reading: lecture notes #3, see also [MU, chapter 7]

Further reading: [Feige, slides on cover time]

- 2018-11-29, Ohad: 2-Universal Hash Families and Perfect
Hashing

Reading: [MU, chapter 13.3] - 2018-12-06, Moni: Maximal Independent Set, Analysis of
Randomized Quicksort, Extractors and Probabilistic Constructions

Reading: lecture notes #5 - 2018-12-13, Moni: Cuckoo Hashing,
*k*-Wise Independence and Extractor Constructions

Reading: class slides - 2018-12-20, Robi: Importance Sampling and Coresets for
Clustering

Reading: lecture notes #7, see also [MR, chapters 11.2], [Munteanu and Schwiegelshohn, survey on coresets]

- 2018-12-27, Robi: Coresets via Uniform and Importance
Sampling

Reading: lecture notes #8, see also [Munteanu and Schwiegelshohn, survey on coresets]

- 2019-01-03, Robi: Edge-Sparsification of Hypergraphs and Some
Occupancy Problems

Reading: lecture notes #9, see also [MR, chapters 3.1, 3.2, 3.6 and 4.1], [DP, chapter 1.6] - 2019-01-10, Moni: TBA
- 2019-01-17, Moni: TBA
- 2019-01-24, Moni: TBA
- 2019-01-31, Robi: Dimension Reduction in l_2

Reading: lecture notes #13

Further reading: [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2]

- 2019-02-07, Robi: The JL Transform and Oblivious Subspace
Embedding

Reading: lecture notes #14

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

- Problem set 1 (posted Nov. 23)

- Problem set 2 (posted Dec. 15, corrected Dec. 24), note the extended due date
- Problem set 3 (posted Jan. 4)

- [MR] Randomized Algorithms by Motwani and Raghavan (errata).
- [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) -- available online 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)

- The Probabilistic Method by Alon and Spencer (3rd Edition).
- Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46.
- Probability and Random Processes (2nd ed.) by Grimmett and Stirzaker.