## Randomized Algorithms (semester 2021A)

Weizmann Institute of Science

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

## Course description

Instructors: Robert Krauthgamer and Moni Naor

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.

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

1. 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].
2. 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].
3. 2020-11-09: Cherno ff Bounds, BPP Ampli fication; 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)
4. 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].
5. 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].
6. 2020-12-07: Streaming Algorithms, K-wise Independence, Card Guessing; Fast JL.
Class material: slides #6, lecture notes #6a, lecture notes #6b.
7. 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.
8. 2020-12-21: Guess the cards, the Lovasz Local Lemma; Oblivious Subspace Embedding.
Class material: slides #8lecture notes #8b
9. 2020-12-28: The Lovasz Local Lemma; in-class exercises on the JL transform.
Class material: slides #9, lecture notes #9a, problem set #1.
10. 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.
11. 2021-01-11: Cuckoo Hashing; Sparse JL Transform.
Class material: slides #11a, lecture notes #11a, slides#11b.
12. 2021-01-18: Bloom Filter, Derandomization, Cuckoo Hashing; Graph Laplacians and Spectral Sparsi fication.
Class material: slides #12a, lecture notes #12a, lecture notes #12b.
13. 2021-01-25: Balls and Bins, Two-Choice Paradigm; Spectral Sparsi fication (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.