Randomized Algorithms (semester 2025A)

[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 155 (no zoom/hybrid)

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.

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

• n/a
  

Lectures

1. 2024-11-04: TBA
   
2. 2022-11-11: TBA
   
3. 2022-11-18: TBA
   
4. 2022-11-25: TBA  
   

Assignments

• TBA
  

Reading material

Relevant textbooks:

• [MR] Randomized Algorithms by Motwani and Raghavan (errata) -- eBook available inside Weizmann.
  
• [MU] Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal (errata).
• [DP] Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi (errata) -- eBook available inside Weizmann.
• [AS] The Probabilistic Method by Alon and Spencer (4th Edition) -- eBook available inside Weizmann (2nd Edition).
• [RY] Communication Complexity and Applications by Rao and Yehudayoff -- eBook available inside Weizmann.
  

Similar courses (many with lecture notes):

• Randomized Algorithms by Nicholas Harvey at UBC (2015)
  
• Randomized Algorithms by Sariel Har-Peled at UIUC (2014)
• Randomized Algorithms and Probabilistic Analysis by James R. Lee at UW (2016)
• Randomized Algorithms by Avrim Blum and Anupam Gupta at CMU (2011)
  
• Randomized Algorithms by David Karger at MIT (2015)

Useful references:

• Concentration by Colin McDiarmid. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46.
• Probability and Random Processes (2nd ed.) by Grimmett and Stirzaker.