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:
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
- [posted 2023-01-31]: Take-home exam schedule: distributed Feb.
27, due within 3 days. The format/instructions will be similar
to previous offerings of this course.
- [posted 2023-01-12]: Problem set 2 was corrected (in Q.#2, the
absolute value was changed and also the hint was expanded)
- [posted 2023-01-10]: lecture notes #6 was slightly updated to
fix typos.
Lectures
- 2022-11-07, Moni: Minimum Cut via Randomized Contractions.
Class material: lecture notes #1, see also [MR,
chapters 1.1].
- 2022-11-14, Moni: 2-SAT and 3-SAT.
Class material: lecture notes #2,see also [MU,
chapter 7].
- 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].
- 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].
- 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].
- 2022-12-12, Robi: Least Squares Regression and Probabilistic
Embedding into Dominating Trees.
Class material: lecture
notes #6.
Further Reading: [Fakcharoenphol,
Rao, and Talwar].
- 2022-12-19, Moni: Card Guessing, Hat Guessing and the Local
Lemma.
- 2022-12-26, Moni: Card Guessing, Hat Guessing and the Local
Lemma (cont'd).
Class material: lecture notes #8.
- 2023-01-02, Moni: Cuckoo Hashing
- 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].
- 2023-01-16, Robi: Coresets for Clustering.
Class material: lecture
notes #11, see also [Munteanu and
Schwiegelshohn, survey on coresets].
- 2023-01-23, Moni: Bloom Filters, Random Graphs, and Limited
Randomness and the Braverman's Result concerning AC0
Class material: lecture notes #12.
- 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]
- 2023-02-06, Robi: Graph Laplacians and Spectral Sparsification
Class material: lecture notes #14.
Assignments
(Should usually be turned in within two weeks)
Reading material
Relevant textbooks:
Similar courses (many with lecture notes):
Useful references: