## 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.
2. 2018-03-25: Distinct elements and point queries.
Homework: problem set #1 below.
2018-04-01: no class (Passover)
3. 2018-04-08: l_2 frequency moment and point queries.
4. 2018-04-15: Amplifying success and hash functions.
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: TBA heavy hitters, compressed sensing, and range queries.
Homework: problem set #3 below.
8. 2018-05-13: l_0-sampling and streaming of graphs.
2018-05-20: no class (Shavuot)
9. 2018-05-27: Connectivity in dynamic graphs and triangle counting
Homework: problem set #4 below.
10. 2018-06-03: Geometric streams and coresets
11. 2018-06-10: Sublinear-time algorithms for sparse graphs .
12. 2018-06-17: Sublinear-time algorithms for sparse graphs (cont'd)
13. 2018-06-24: Lower bounds via communication complexity of Indexing
Homework: problem set #5 below.
14. 2018-07-01: More streaming lower bounds

## Assignments

(Should usually be turned in within two weeks)