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

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: TBA heavy hitters, compressed sensing, and range 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, lectures #5; Nelson, lecture #7]
    2018-05-20: no class (Shavuot)
  9. 2018-05-27: TBA
  10. 2018-06-03: TBA
  11. 2018-06-10: TBA
  12. 2018-06-17: TBA
  13. 2018-06-24: TBA
  14. 2018-07-01: TBA

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: