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

**Instructors:** Robert
Krauthgamer and Moni Naor

**Grader:** Lior.Kamma (at weizmann.ac.il)

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

**First class: **Nov. 10, 2016

**FGS code:** 20174101

**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 take-home exam. Distributed on
February 26, 2017 at noon (by email), to be handed-in within 48
hours.

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

** Previous offerings:**

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

- 2017-02-06: The date of the final has changed, see above.

- 2017-01-26: The final will be a take-home exam, see above for
more details.

- 2016-11-10, Moni: Min-Cut Algorithm, Closest Pairs,
(Multi)-Set Equality.

Reading: lecture notes #1

- 2016-11-17, Moni: Maximal Independent Set, Analysis of
Randomized Quicksort, Extractors and Probabilistic
Constructions

Reading: lecture notes #2

- 2016-11-24, Moni: Ball and bins, Martingales, Concentration
bounds and Bloom Filters

Reading: lecture notes #3

- 2016-12-01, Robi: Random Walks on Graphs

Reading: lecture notes #4, 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] - 2016-12-08, Robi: Effective Resistance and Algorithms for
SAT

Reading: lecture notes #5, see also [MU, chapter 7] - 2016-12-15, Robi: Distance Oracles and Distance Labeling via
Embedding

Reading: lecture notes #6

Further reading: [Jiri Matousek (book), chapter 15, also here]

- 2016-12-22, Robi: Dimension Reduction in l_2

Reading: lecture notes #7

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

2016-12-29: no class (HANNUKKA) - 2017-01-05, Moni: TBA
- 2017-01-12, Moni: TBA
- 2017-01-19, Lior: Metric Embeddings into Random Trees

Reading: lecture notes #10

- 2017-01-26, Robi: Graph Laplacians and Spectral Sparsification

Reading: lecture notes #11

Further reading: [Spielman, lecture 17] and [Harvey, Cargese Workshop lecture notes]

- 2017-02-02, Moni: TBA
- 2017-02-09, Robi: The JL Transform and Oblivious Subspace
Embedding

Reading: lecture notes #13

Further reading: [Woodruff, section 2, also here]

- Problem set 1 (posted Dec. 10)

- Problem set 2 (posted Dec. 24)

- Problem set 3 (posted Feb. 15)

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

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