## Randomized Algorithms (semester 2017A)

Weizmann Institute of Science

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

## Course description

Instructors: Robert Krauthgamer and Moni Naor

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.

## 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

1. 2016-11-10, Moni: Min-Cut Algorithm, Closest Pairs, (Multi)-Set Equality.
2. 2016-11-17, Moni: Maximal Independent Set, Analysis of Randomized Quicksort, Extractors and Probabilistic Constructions
3. 2016-11-24, Moni: Ball and bins, Martingales, Concentration bounds and Bloom Filters
4. 2016-12-01, Robi: Random Walks on Graphs
Further reading: [Levin, Peres, and Wilmer, chapter 9], [Doyle and Snell, also as arXiv:math/0001057], [Lyons and Peres, chapter 2]
5. 2016-12-08, Robi: Effective Resistance and Algorithms for SAT
6. 2016-12-15, Robi: Distance Oracles and Distance Labeling via Embedding
Further reading: [Jiri Matousek (book), chapter 15, also here]
7. 2016-12-22, Robi: Dimension Reduction in l_2
Further reading: [Dasgupta and Gupta], [Jiri Matousek (lecture notes), chapter 2]
2016-12-29: no class (HANNUKKA)
8. 2017-01-05, Moni: TBA
9. 2017-01-12, Moni: TBA
10. 2017-01-19, Lior: Metric Embeddings into Random Trees
11. 2017-01-26, Robi: Graph Laplacians and Spectral Sparsification
Further reading: [Spielman, lecture 17] and [Harvey, Cargese Workshop lecture notes]
12. 2017-02-02, Moni: TBA
13. 2017-02-09, Robi: The JL Transform and Oblivious Subspace Embedding