Sublinear Time and Space Algorithms (semester 2020B)

Weizmann Institute of Science

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

Course description

Instructor: Robert Krauthgamer

Grader: TBA

When and where: Mondays 14:15-16:00, Ziskind Lecture Room 1

First class: March 23, 2020

FGS code: 20204182

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.


There will be a take-home exam.

Previous offerings:



  1. TBA


(Should usually be turned in within two weeks)

Reading material

Surveys and lecture notes:

Similar/related courses (many with lecture notes):

Useful references: