Randomized Algorithms (semester 2023A)

Weizmann Institute of Science

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

Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: TBA 

When and where: Monday 14:15-17:00, Ziskind Lecture Room 1 (no zoom/hybrid)

First class: Nov. 7, 2022 

FGS code: 20234051

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: The final assignment will be a take-home exam.

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

Previous offerings:



  1. 2022-11-07, Moni: Minimum Cut via Randomized Contractions.
    Class material: lecture notes #1, see also [MR, chapters 1.1].
  2. 2022-11-14, Moni: 2-SAT and 3-SAT.
    Class material: lecture notes #2,see also [MU, chapter 7].
  3. 2022-11-21, Moni: Existential Proofs via Probabilistic Constructions, Large Deviation Bounds and Communication.
    Class material: lecture notes #3, see also [AS, appendix A] and [RY].
  4. 2022-11-28, Robi: Dimension Reduction in l_2, JL and fast JL.
    Class material: lecture notes #4
    Further Reading: [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2].
  5. 2022-12-05, Robi: JL Transform and Oblivious Subspace Embedding.
    Class material: lecture notes #5.
    Further Reading: [Woodruff, section 2, also as arXiv:1411.4357].
  6. 2022-12-12, Robi: Least Squares Regression and Probabilistic Embedding into Dominating Trees.
    Class material: lecture notes #6.
    Further Reading: [Fakcharoenphol, Rao, and Talwar].
  7. 2022-12-19, Moni: Card Guessing, Hat Guessing and the Local Lemma.
  8. 2022-12-26, Moni: Card Guessing, Hat Guessing and the Local Lemma (cont'd).
    Class material: lecture notes #8.
  9. 2023-01-02, Moni: Cuckoo Hashing
  10. 2023-01-09, Robi: Probabilistic Embedding into Dominating Trees (cont'd) and Importance Sampling.
    Class material: lecture notes #10, see also [MR, chapter 11.2].
  11. 2023-01-16, Robi: Coresets for Clustering.
    Class material: lecture notes #11, see also [Munteanu and Schwiegelshohn, survey on coresets].
  12. 2023-01-23, Moni: Bloom Filters, Random Graphs, and Limited Randomness and the Braverman's Result concerning AC0
    Class material: lecture notes #12.
  13. 2023-01-30, Robi: Concentration Bounds and Edge-Sparsification of Hypergraphs
    Class material: lecture notes #13, see also [MR, chapter 4.1], [DP, chapter 1.6]
  14. 2023-02-06, Robi: Graph Laplacians and Spectral Sparsification
    Class material: lecture notes #14


(Should usually be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses (many with lecture notes):

Useful references: