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

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 13, 2016

FGS code: 20164012

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.

Exam (final assignment): Here is the final assignment itself.

## Announcements

• [posted 2016-05-31] problem set 4 was slightly corrected (in Q.#3)
• [posted 2016-05-29] final assignment schedule: distributed on June 28, and due within 5 days
• [posted 2016-05-15] no class on June 5 and 19
• [posted 2016-04-03] problem set 1 was slightly corrected
• [posted 2016-04-03] no class April 10, 17 and 24.
• [posted 2016-03-21] class of April 3 will take place in room 261
• [posted 2016-03-13] no class on 2016-03-20
• [posted 2016-03-13] most future classes will be extended till 13:00

## Lectures

1. 2016-03-13: data-stream algorithms, probabilistic counting, reservoir sampling, frequency vectors
2016-03-20: no class
2. 2016-03-27: distinct elements, point queries and hash functions
[homework: problem set #1 below]
3. 2016-04-03: l_2 frequency moment and point queries, heavy hitters, and compressed sensing
2016-04-10: no class (faculty retreat)
2016-04-17: no class
2016-04-24: no class (Passover)
4. 2016-05-01: precision Sampling and high frequency moments
5. 2016-05-08: l_0-sampling and connectivity in dynamic graphs
[homework: problem set #2 below]
6. 2016-05-15: triangle counting, geometric streams and coresets
7. 2016-05-22: Sublinear-Time Algorithms for Sparse Graphs
[homework: problem set #3 below]
8. 2016-05-29: Lower Bounds via Communication Complexity
[homework: problem set #4 below]
2016-06-05: no class
2016-06-12: no class (Shavout)
2016-06-19: no class
9. 2016-06-26: More Lower Bounds and Algorithms for Sequences

## Assignments

(Should usually be turned in within two weeks)