## Sublinear Time and Space Algorithms (semester 2018B)

Weizmann Institute of Science

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

## Course description

Instructor: Robert Krauthgamer

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

• [posted 2018-07-14] to get a copy of the final assignment, email me by July 15
• [posted 2018-06-18] lecture notes #12 was expanded (added last lemma and proof)
• [posted 2018-06-01] problem set 4 was slightly corrected (Q. #1,2 are now specify explicitly the desired success probability)
• [posted 2018-05-28] final assignment schedule: distributed on July 15 (by noon), due within 4 days.
• [posted 2018-04-19] problem set 2 was corrected (due date was wrong)
• [posted 2018-03-18] for a quick idea about the topics of the class, watch the 15-minute YouTube talk "Some Important Streaming Algorithms You Should Know About" by Ted Dunning (MapR).

## 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.
6. 2018-04-29: Compressed Sensing via RIP matrices and Basis Pursuit.
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)