Randomized Algorithms (semester 2025A)

Weizmann Institute of Science

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


Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: Guy Kornowski (at weizmann.ac.il)

When and where: Monday 14:15-17:00, Ziskind Lecture Room 155 

First class: Nov. 4, 2024 

FGS code: 20254071

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.
Here is the final exam itself.

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

Previous offerings:
http://www.wisdom.weizmann.ac.il/~robi/teaching/2023a-RandomizedAlgorithms
http://www.wisdom.weizmann.ac.il/~robi/teaching/2021a-RandomizedAlgorithms
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


Lectures

  1. 2024-11-04, Moni: Introduction and the Min Cut algorithm.
    Class material: lecture notes #1.  
  2. 2024-11-11, Moni:  A better exponential time algorithm for satisfiability, streaming, Freivalds Matrix Checking SAT.
    Class material: lecture notes #2.
  3. 2024-11-18, Moni: Large Deviation Bounds, Communication Complexity and Existential Proofs via Probabilistic Construction Communication.
    Class material: lecture notes #3.
  4. 2024-11-25, Robi: Dimension Reduction in l_2 fast JL.
    Class material: lecture notes #4.
  5. 2024-12-02, Robi: JL Transform, Oblivious Subspace Embedding, and Least Squares Regression.
    Class material: lecture notes #5.
  6. 2024-12-09, Robi: Nearest Neighbor Search in l_1.
    Class material: lecture notes #6.
  7. 2024-12-16, Robi: Probabilistic Embedding into Dominating Trees.
    Class material: lecture notes #7.
  8. 2024-12-23, Robi + Moni: Probabilistic Embedding into Dominating Trees (cont'd) + Cuckoo Hashing.
    Class material: lecture notes #8a. Class +  lecture notes #8b.
  9. 2024-12-30, Moni: Cuckoo Hashing (cont'd) and Bloom Filters.
    Class material: lecture slides #9.
  10. 2025-01-06, Moni: Lovasz Local Lemma.
    Class material: lecture slides #10.
  11. 2025-01-14, Moni: Card Guesing.
    Class material: lecture slides #11.
  12. 2025-01-20, Robi: Importance Sampling, Counting DNF solutions, and Coresets for Clustering.
    Class material: lecture notes #12.
  13. 2025-01-27, Robi: Coresets via Importance Sampling.
    Class material: lecture notes #13.

Assignments

(Should usually be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses (many with lecture notes):

Useful references: