Sublinear Time and Space Algorithms (semester 2018B)

Weizmann Institute of Science

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


Course description

Instructor: Robert Krauthgamer

Grader: Chen Attias

When and where: Sundays 10:15-12:00, Ziskind Lecture Room 1

First class: March 18, 2018

FGS code: 20184022

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.

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

Final:
There will be a final assignment (take-home exam). Here is the final assignment itself.

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


Announcements


Lectures

  1. 2018-03-18: Data-stream algorithms, probabilistic counting, reservoir sampling, frequency vectors.
    Reading: lecture notes #1. See also Andoni, lecture #1; Nelson, lecture #1; Chekuri, lecture #1.
  2. 2018-03-25: Distinct elements and point queries.
    Reading: lecture notes #2. See also Andoni, lectures #2+3; Nelson, lecture #2+6; Chekuri, lecture #2+6.
    Homework: problem set #1 below.
    2018-04-01: no class (Passover)
  3. 2018-04-08: l_2 frequency moment and point queries.
    Reading: lecture notes #3. See also Andoni, lectures #3+4; Nelson, lecture #3+6+7; Chekuri, lecture #4+6.
  4. 2018-04-15: Amplifying success and hash functions.
    Reading: lecture notes #4. See also Andoni, lecture #2; Nelson, lecture #2; Chekuri, lecture #2.
    Homework: problem set #2 below.
  5. 2018-04-22: Heavy hitters, compressed sensing, and range queries.
    Reading: lecture notes #5. See also Chekuri, lecture #6+7.
  6. 2018-04-29: Compressed Sensing via RIP matrices and Basis Pursuit.
    Reading: lecture notes #6. See also Nelson, lecture #19.
  7. 2018-05-06: Precision Sampling and High Frequency Moments queries.
    Reading: lecture notes #7. See also Andoni, lectures #4+5; Nelson, lecture #4+5.
    Homework: problem set #3 below.
  8. 2018-05-13: l_0-sampling and streaming of graphs.
    Reading: lecture notes #8. See also Andoni, lecture #5; Nelson, lecture #7.
    2018-05-20: no class (Shavuot)
  9. 2018-05-27: Connectivity in dynamic graphs and triangle counting
    Reading: lecture notes #9. See also Andoni, lectures #5+6; Chakrabarti, chapter #15.
    Homework: problem set #4 below.
  10. 2018-06-03: Geometric streams and coresets
    Reading: lecture notes #10. See also also Chakrabarti, chapter #12; Beame, lectures #13+14.
  11. 2018-06-10: Sublinear-time algorithms for sparse graphs .
    Reading: lecture notes #11. See also survey by Czumaj and Sohler.
  12. 2018-06-17: Sublinear-time algorithms for sparse graphs (cont'd)
    Reading: lecture notes #12. See also paper by Hassidim, Kelner, Nguyen and Onak.
  13. 2018-06-24: Lower bounds via communication complexity of Indexing
    Reading: lecture notes #13; see also Nelson, lecture #9; Beame, lectures #11+12
    Homework: problem set #5 below.
  14. 2018-07-01: More streaming lower bounds 
    Reading: lecture notes #14; 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: