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.

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


Lectures

  1. 2016-11-10, Moni: Min-Cut Algorithm, Closest Pairs, (Multi)-Set Equality.
    Reading: lecture notes #1
  2. 2016-11-17, Moni: Maximal Independent Set, Analysis of Randomized Quicksort, Extractors and Probabilistic Constructions 
    Reading: lecture notes #2
  3. 2016-11-24, Moni: Ball and bins, Martingales, Concentration bounds and Bloom Filters
    Reading: lecture notes #3
  4. 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]
  5. 2016-12-08, Robi: Effective Resistance and Algorithms for SAT 
    Reading: lecture notes #5, see also [MU, chapter 7]
  6. 2016-12-15, Robi: Distance Oracles and Distance Labeling via Embedding
    Reading: lecture notes #6 
    Further reading: [Jiri Matousek (book), chapter 15, also here]
  7. 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)
  8. 2017-01-05, Moni: TBA
  9. 2017-01-12, Moni: TBA
  10. 2017-01-19, Lior: Metric Embeddings into Random Trees 
    Reading: lecture notes #10
  11. 2017-01-26, Robi: Graph Laplacians and Spectral Sparsification
    Reading: lecture notes #11
    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
    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: