Randomized Algorithms (semester 2021A)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Course description
Instructors: Robert
Krauthgamer and Moni Naor
Grader: n/a
When and where: Monday 14:15-17:00, taught via Zoom Ziskind
Lecture Room 1
First class: Oct. 26, 2020
FGS code: 20214051
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).
Here is the final exam itself.
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2021a-RandomizedAlgorithms
Previous offerings:
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
Announcements
- 2020-12-07: Take-home
exam schedule: distributed Feb. 1, due within 1
week
- 2020-10-19: The "Grade Breakdown" in the FGS course details
(the method of determining the grade in the course) has changed
and it will be based 100% on a final assignment (take-home
exam).
Lectures
- 2020-10-26, Moni + Robi: Minimum Cut via Randomized
Contractions; Random Walks on Graphs.
Class material: slides
#1, lecture notes #1a,
lecture notes #1b, see also [MR,
chapters 1.1 and 6.3] and [MU, chapters 1.4 and 7.4].
- 2020-11-02: 2-SAT, 3-SAT and Complexity Classes; Cover Time.
Class material: slides
#2, lecture notes #2a,
lecture notes #2b, see also [MR,
chapters 6.1, 6.6, 6.5] and [MU, chapters 7.1. and 7.4].
- 2020-11-09: Chernoff Bounds, BPP Amplification; Electrical
Networks.
Class material: slides
#3, lecture notes #3a,
lecture notes #3b, see also [MR,
chapters 1.5, 7.1 and 6.4], [AS, Appendix A] and [MU, chapters
1.3].
2020-11-16: no class (SIGD)
- 2020-11-23: Streaming Algorithms, Multiset equality; Effective
Resistance.
Class material: slides
#4, lecture notes #4a,
lecture notes #4b, see also [MR,
chapters 6.4].
Further reading: [Levin, Peres,
and Wilmer, chapter 9], [Doyle
and Snell, also as arXiv:math/0001057],
[Lyons and
Peres, chapter 2].
Further reading: [Feige,
slides on cover time].
- 2020-11-30: Streaming Algorithms; Dimension Reduction in l_2.
Class material: slides
#5, lecture notes #5a,
lecture notes #5b.
Further reading: [Rao and
Yehudayoff, chapter 6, eBook
available inside Weizmann], [Dasgupta and Gupta],
[Jiri
Matousek (lecture notes), chapter 2].
- 2020-12-07: Streaming Algorithms, K-wise Independence, Card
Guessing; Fast JL.
Class material: slides
#6, lecture notes #6a,
lecture notes #6b.
- 2020-12-14: How To Guess Cards with Little Memory; Fast JL and
the JL Transform.
Class material: slides
#7, lecture notes #7a,
lecture notes #7b.
- 2020-12-21: Guess the cards, the Lovasz Local Lemma; Oblivious
Subspace Embedding.
Class material: slides
#8, lecture notes #8b.
- 2020-12-28: The Lovasz Local Lemma; in-class exercises on the
JL transform.
Class material: slides
#9, lecture notes #9a,
problem set #1.
- 2021-01-04: The Algorithmic Lovasz Local Lemma and Cuckoo
Hashing; Regression via OSE, Importance Sampling.
Class material: slides
#10, lecture notes
#10a, lecture notes #10b.
- 2021-01-11: Cuckoo Hashing; Sparse JL Transform.
Class material: slides
#11a, lecture notes
#11a, slides#11b.
- 2021-01-18: Bloom Filter, Derandomization, Cuckoo Hashing;
Graph Laplacians and Spectral Sparsification.
Class material: slides
#12a, lecture notes
#12a, lecture notes #12b.
- 2021-01-25: Balls and Bins, Two-Choice Paradigm; Spectral
Sparsification (cont'd).
Class material: slides
#13a, lecture notes
#13a, lecture notes #13b.
Assignments
(Should usually be turned in within two weeks)
- There will be no requirement to hand-in assignments during the
semester. Any exercises/homework will be for self-practice and
will not be checked.
Reading material
Relevant textbooks:
Similar courses (many with lecture notes):
Useful references: