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

**Instructors:** Robert
Krauthgamer and Moni Naor

**Grader:** Gilad.Tsur (at weizmann.ac.il)

**When and where:** Sundays, 2-5pm, Ziskind Lecture Room 1

**First class: **November 4, 2012

**FGS code:** 20134151

**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 17, 2013 (at 10am).

Here is the final exam itself.

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

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

- The exam will take place at
**FGS room B**.

- 2012-11-04, Robi: Randomized quicksort. Markov’s
inequality and Chernoff-Hoeffding concentration bounds. Some
occupancy problems. [lecture notes #1]
- Additional reading: [MR, chapters 1, 3.1 and 4.1], [DP, chapters 3.3.3 and 1.6]

- 2012-11-11, Robi: The second moment, more occupancy problems,
data-stream algorithms for L_2-norm and for point queries.
[lecture notes #2]
- Additional reading: [MR, chapters 3.1, 3.2, 3.6], [MU, chapter 3.3], course notes (by Indyk) lectures 2 and 4; encyclopedia of database systems entry (by Cormode).

- 2012-11-18, Robi: Proof of Hoeffding's bound, heavy hitters via point queries, and sketching algorithms. [lecture notes #3]
- Additional reading: [DP, chapter 1.5], same as previous class.
- 2012-11-25, Moni: Bloom filter, maximal independent set, closest points.
- Additional reading: bloom filter survey, lecture notes (by Roger Wattenhofer), Klienberg-Tardos's book chapter.
- 2012-12-02, Moni: Martingales, Closest Pairs, Hash Tables,
Existential Proofs and Codes. [lecture
notes #5]
- Additional reading:

- Noga Alon, Martin Dietzfelbinger, Peter B. Miltersen, Erez Petrank, and Gabor Tardos, Linear Hashing, Journal of the ACM, Vol. 46(5), 1999.
- J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. Syst. Sci. 18 (1979) 143--154.
- Eric Demaine, Lecture 10 in course 6.851: Advanced Data Structures (Spring'12) on Dictionaries.
- Paul Erdos, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (4), 1947, pp. 292-–294.
- Jon Kleinberg and Eva Tardos, Algorithm Design. Addison
Wesley, 2006. Chapter
13.

- Dick Lipton's blog, Rabin Flips a Coin, March 2009.
- Rene Schoof, Four primality testing algorithms, arXiv 0801.3840.

2012-12-09: no class (HANNUKKAH)

- Additional reading:
- 2012-12-16, Moni: Cuckoo Hashing, construction of k-wise
independent hash functions, random codes [slides]
- Additional reading:
- The original Journal paper: R. Pagh and F. F.
Rodler, Cuckoo
Hashing.

- Patrascu and Thorup's work on The
Power of Simple Tabulation Hashing.

- Blogs on cuckoo hashing: by Mihai Patrascu: here;
and by Michael Mitzenmacher: part1,
part2,
part3.

- 2012-12-23, Robi: Global Minimum Cuts and Edge Sparsification
[lecture notes #7]

- Additional reading: [MR, chapters 1.1 and 10.2], [MU, chapter 1.4], the Benczur-Karger paper.

- 2012-12-30, Robi: Edge Sparsification (cont'd) and Distance
Oracles [lecture notes #8]

- Additional reading: the Benczur-Karger
paper, the Thorup-Zwick
paper.

- Additional reading: the Benczur-Karger
paper, the Thorup-Zwick
paper.
- 2013-01-06, Moni: The power of two choices and Markov chains

- Additional reading: [MU, chapters 14 and 7], a survey
on two choices by Mitzenmacher, Richa and Sitaraman.

- Additional reading: [MU, chapters 14 and 7], a survey
on two choices by Mitzenmacher, Richa and Sitaraman.
- 2013-01-13, Moni: Markov Chains: Random Walks, Mixing Times
and Coupling

- Additional reading: [MU, chapters 7 and 11]; Manuscript
on Mixing time by Levin, Peres and Wilmer; Analysis
of the Thorp Shuffle by Morris, Rogaway and Stegers.

- Additional reading: [MU, chapters 7 and 11]; Manuscript
on Mixing time by Levin, Peres and Wilmer; Analysis
of the Thorp Shuffle by Morris, Rogaway and Stegers.
- 2013-01-20, Robi: Importance Sampling, and the Local Lemma [lecture notes #11]
- Additional reading for importance sampling: [MR, chapters 11.2]; class notes by Amin Saberi.
- Additional reading for LLL: class
notes by Joel Spencer, and class
notes by Uri Feige; blog
post by Terry Tao.

- 2013-01-27, Robi: Nearest Neighbor Searching (NNS) in High
Dimension [lecture notes #12]

- Additional reading: the Indyk-Motwani paper, the Kushilevitz-Ostrovsky-Rabani paper.

- 2013-02-07, Moni: Minmax theorem and its applications to lower
bounds in randomized algorithms (Yao's principle) [MR, Chapter
2.1-2.2], competitive analysis of online algorithms [MR, Chapter
13], analysis of stable matching [MR, Chapters 3.5-3.6].

- problem set 1 (posted Nov. 5, concentration bounds)
- problem set 2 (posted Nov. 20)
- problem set 3 (posted Dec. 6, due Dec. 23)
- problem set 4 (posted Dec. 31)
- problem set 5 (posted Jan. 28, due Feb.
13)

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