Randomized Algorithms (semester 2017A)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures]
[Assignments] [Reading material]
Course description
Instructors: Robert
Krauthgamer and Moni Naor
Grader: Lior.Kamma (at weizmann.ac.il)
When and where: Thursday 14:15-17:00, Ziskind Lecture Room
1
First class: Nov. 10, 2016
FGS code: 20174101
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 take-home exam. Distributed on
February 26, 2017 at noon (by email), to be handed-in within 48
hours.
Here is the final exam itself.
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2017a-RandomizedAlgorithms
Previous offerings:
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
- 2017-02-06: The date of the final has changed, see above.
- 2017-01-26: The final will be a take-home exam, see above for
more details.
Lectures
- 2016-11-10, Moni: Min-Cut Algorithm, Closest Pairs,
(Multi)-Set Equality.
Reading: lecture notes #1
- 2016-11-17, Moni: Maximal Independent Set, Analysis of
Randomized Quicksort, Extractors and Probabilistic
Constructions
Reading: lecture notes #2
- 2016-11-24, Moni: Ball and bins, Martingales, Concentration
bounds and Bloom Filters
Reading: lecture notes #3
- 2016-12-01, Robi: Random Walks on Graphs
Reading: lecture notes #4, 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]
- 2016-12-08, Robi: Effective Resistance and Algorithms for
SAT
Reading: lecture notes #5, see also
[MU, chapter 7]
- 2016-12-15, Robi: Distance Oracles and Distance Labeling via
Embedding
Reading: lecture notes #6
Further reading: [Jiri
Matousek (book), chapter 15, also here]
- 2016-12-22, Robi: Dimension Reduction in l_2
Reading: lecture notes #7
Further reading: [Dasgupta
and Gupta], [Jiri
Matousek (lecture notes), chapter 2]
2016-12-29: no class (HANNUKKA)
- 2017-01-05, Moni: TBA
- 2017-01-12, Moni: TBA
- 2017-01-19, Lior: Metric Embeddings into Random Trees
Reading: lecture notes #10
- 2017-01-26, Robi: Graph Laplacians and Spectral Sparsification
Reading: lecture notes #11
Further reading: [Spielman,
lecture 17] and [Harvey,
Cargese Workshop lecture notes]
- 2017-02-02, Moni: TBA
- 2017-02-09, Robi: The JL Transform and Oblivious Subspace
Embedding
Reading: lecture notes #13
Further reading: [Woodruff,
section 2, also here]
Assignments
(Should usually be turned in within two weeks)
Reading material
Relevant textbooks:
Similar courses (many with lecture notes):
Useful references: