Randomized Algorithms (semester 2019A)

Weizmann Institute of Science

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

Course description

Instructors: Robert Krauthgamer and Moni Naor

Grader: Ohad.Trabelsi (at weizmann.ac.il)

When and where: Thursday 14:15-17:00, Ziskind Lecture Room 1

First class: Nov. 8, 2018

FGS code: 20194201

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/2019a-RandomizedAlgorithms

Previous offerings:



  1. 2018-11-08, Moni: (Multi)-Set Equality, Closest Pair, Minimum Cut.
    Reading: lecture notes #1
  2. 2018-11-15, Robi: Random Walks on Graphs
    Reading: lecture notes #2, see also [MR, chapter 6]
    Further reading: [Levin, Peres, and Wilmer, chapter 9], [Doyle and Snell, also as arXiv:math/0001057], [Lyons and Peres, chapter 2]
  3. 2018-11-22, Robi: Effective Resistance and an Algorithm for 2SAT
    Reading: lecture notes #3, see also [MU, chapter 7]
    Further reading: [Feige, slides on cover time]
  4. 2018-11-29, Ohad: 2-Universal Hash Families and Perfect Hashing
    Reading: [MU, chapter 13.3]
  5. 2018-12-06, Moni: Maximal Independent Set, Analysis of Randomized Quicksort, Extractors and Probabilistic Constructions
    Reading: lecture notes #5
  6. 2018-12-13, Moni: Cuckoo Hashing, k-Wise Independence and Extractor Constructions
    Reading: class slides 
  7. 2018-12-20, Robi: Importance Sampling and Coresets for Clustering
    Reading: lecture notes #7, see also [MR, chapters 11.2], [Munteanu and Schwiegelshohn, survey on coresets]
  8. 2018-12-27, Robi: Coresets via Uniform and Importance Sampling 
    Reading: lecture notes #8, see also [Munteanu and Schwiegelshohn, survey on coresets]
  9. 2019-01-03, Robi: Edge-Sparsification of Hypergraphs and Some Occupancy Problems  
    Reading: lecture notes #9, see also [MR, chapters 3.1, 3.2, 3.6 and 4.1], [DP, chapter 1.6]
  10. 2019-01-10, Moni: TBA
  11. 2019-01-17, Moni: TBA
  12. 2019-01-24, Moni: TBA
  13. 2019-01-31, Robi: Dimension Reduction in l_2
    Reading: lecture notes #13
    Further reading: [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2]
  14. 2019-02-07, Robi: The JL Transform and Oblivious Subspace Embedding
    Reading: lecture notes #14
    Further reading: [Woodruff, section 2, also as arXiv:1411.4357


(Should usually be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses (many with lecture notes):

Useful references: