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

**Instructors:** Robert
Krauthgamer and Moni Naor

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

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

**First class: **November 4, 2014

**FGS code:** 20154371

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

**Exam:** February 24, 2015 (at 10am, Ziskind #1).

Here is the final exam itself.

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

Previous offerings:

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

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

- There will be no class on 2015-01-13 (due to ITCS conference)
- Additional class on 2015-02-17 between 10:00-13:00 (room:
Ziskind #1).

- 2014-11-04, Moni: Min Cut Algorithm, Closest Pairs,
(Multi)-Set Equality [lecture notes #1]

- 2014-11-11, Moni: Maximal Independent Set, Analysis of
Randomized Quicksort, Universal Hashing and Dictionaries,
Concentration bounds- Chernoff [lecture
notes #2]

- 2014-11-18, Moni: Random graphs, Azuma's inequality, and Bloom
filters

- 2014-11-25, Moni: Hashing, Hamiltonicity of a random graph,
Balls and Bins

- 2014-12-02, Robi: Edge Sparsification for Cuts [lecture notes #5]

- 2014-12-09, Robi: Distance Oracles and Distance Labeling [lecture notes #6]

- 2014-12-16, Robi: Data streams, the AMS algorithm for l_2-norm, l_1-point queries, and heavy hitters [lecture notes #7]
- 2014-12-23, Robi: l_p-norm, p>2, of a data stream [lecture notes #8]

- 2014-12-30, Robi: Dimension Reduction in l_2, Sketching, and
NNS in l_1 (with logarithmic query time) [lecture
notes #9]

- 2015-01-06, Moni: Cuckoo Hashing

2015-01-13: no class (due to ITCS) - 2015-01-20: Moni: Oblivious RAM, Random walk algorithm for
2-SAT and 3-SAT

- 2015-01-27, Robi: Compressed Sensing and RIP matrices [lecture notes #12]
- 2015-02-17, Robi: Communication Complexity Lower Bounds [lecture notes #13]

- problem set 1 (posted Nov. 18)
- problem set 2 (posted Dec. 17)
- problem set 3 (posted Dec. 31)

- [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 (2012)

- Randomized Algorithms by Sariel Har-Peled at UIUC (2010)
- Randomized Algorithms and Probabilistic Analysis by James R. Lee at UW (2008)
- Randomized Algorithms by Anupam Gupta and Shuchi Chawla at CMU (2004)
- Randomized Algorithms by David Karger at MIT (2007)
- Randomized Algorithms by Avrim Blum at CMU (1997)

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