Sublinear Time and Space Algorithms (semester 2022B)

Weizmann Institute of Science

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


Course description

Instructor: Robert Krauthgamer

Grader: Shay.Sapir (at weizmann.ac.il) 

When and where: Mondays 14:15-16:00, Ziskind Lecture Room 1

First class: March 28, 2022

FGS code: 20224092

Syllabus: The course will cover algorithms whose running time and/or space requirement is sublinear in the input size. Such algorithms can view only a small portion of the entire input, but they are particularly suitable for analyzing massive data sets. In recent years, this approach has been successfully used in several areas, including graph theory, linear algebra, combinatorial optimization, geometry, and string matching.

Prerequisites: Basic knowledge of algorithms, probability and linear algebra at an undergraduate level.

Final: There will be a take-home exam. Distributed morning of July 18 (via email), due within 72 hours. Its format will be similar to previous years.
Here is the final assignment itself.

Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2022b-SublinearAlgorithms

Previous offerings:

http://www.wisdom.weizmann.ac.il/~robi/teaching/2020b-SublinearAlgorithms/
http://www.wisdom.weizmann.ac.il/~robi/teaching/2018b-SublinearAlgorithms/
http://www.wisdom.weizmann.ac.il/~robi/teaching/2016b-SublinearAlgorithms/

Announcements


Lectures

  1. 2022-03-28: Data-Stream Algorithms, Probabilistic Counting.
    Reading: lecture notes #1. See also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1; and paper by Nelson and Yu.
  2. 2022-04-04: Reservoir Sampling, Frequency Vectors, Distinct Elements.
    Reading: lecture notes #2. See also Andoni, lectures #2; Nelson, lecture #2; Chekuri, lecture #2.
    Homework: problem set #1 below.
  3. 2022-04-11: Frequency Moments (l_2) and Point Queries (l_1).
    Reading: lecture notes #3. See also Andoni, lectures #3+4; Nelson, lecture #3+6; Chekuri, lecture #4+6.
  4. 2022-04-25: Amplifying success probability, l_2 Point Queries, and Hash Functions.
    Reading: lecture notes #4. See also Andoni, lecture #3+4; Nelson, lecture #2+6+7; Chekuri, lecture #6.
    Homework: problem set #2 below.
    2022-05-02: no class (Eid al-Fitr)
  5. 2022-05-09: Adversarially Robust Streaming, Flip-Number and Sparse-Dense Tradeoff.
    Reading: lecture notes #5. See also two papers by Ben-Eliezer, Jayaram, Woodruff, and Yogev, and by Ben-Eliezer, Eden, and Onak.
    2022-05-16: no class (faculty retreat)
    2022-05-23: no class
  6. 2022-05-30: Dynamic Geometric Streams and Euclidean MST.
    Reading: lecture notes #6. See also paper by Indyk.
  7. 2022-06-06: Euclidean MST (cont'd) and l_0-sampling
    Reading: lecture notes #7. See also Nelson, lecture #7.
    Homework: problem set #3 below.
  8. 2022-06-13: Streaming of Graphs and Connectivity in Dynamic Graphs.
    Reading: lecture notes #8. See also Andoni, lecture #5+6; Nelson, lecture #7.
  9. 2022-06-20: Sublinear-time algorithms for sparse graphs.
    Reading: lecture notes #9. See also survey by Czumaj and Sohler.
  10. 2022-06-27: Sublinear-time algorithms for maximum matching and vertex cover 
    Reading: lecture notes #10. See also paper by Hassidim, Kelner, Nguyen and Onak.
    Homework: problem set #4 below.
  11. 2022-07-04: Sublinear-time algorithms for vertex cover 
    Reading: lecture notes #11.
  12. 2022-07-11: Communication Complexity and Streaming Lower Bounds 
    Reading: lecture notes #12; see also Nelson, lecture #9+10; Beame, lectures #11+12.

Assignments

(Should usually be turned in within two weeks)

Reading material

Surveys and lecture notes:

Similar/related courses (many with lecture notes):

Useful references:

Other: