Sublinear Algorithms

Advanced Course

Basic Information

Lectures:	Thursday, 16:15 - 18:00
Lecturer:	Karl Bringmann, Vasileios Nakos
First lecture:	May 07
Tutorials:	every second Monday, 16:15 - 18:00
Assistant:	Nick Fischer
First tutorial:	May 11
Credits:	5
Exam:	Oral Exam on July 20
Prerequisites:	We assume mathematical maturity and comfort with basic probability theory. We also assume basic knowledge in algorithms. Therefore, required prerequisite is a basic lecture in algorithms (such as "Grundzüge von Algorithmen und Datenstrukturen"). The core lecture "Algorithms and Data Structures" would be helpful, but is not a formal requirement.

News

Due to technical problems the lecture on May 28 has been cancelled. We therefore move all tutorials and lectures back by one week, resulting in some changes to the schedule (see "Tentative Schedule" below).
The course will make extensive use of randomization. Therefore, we have collected background on probability theory and how to use it in algorithm design in a "Primer to Randomness", which can be found in the Material section below. We suggest that you read at least the first half of this document before the first lecture, and the whole document before the second lecture.
Please subscribe to the following mailing list, which we will use to announce details of the virtual lectures and tutorials: https://lists.mpi-inf.mpg.de/listinfo/sublinear
Lectures and tutorials will be given via a standard teleconference system. It is possible to participate in the whole course virtually, except possibly in the exams.

Description

For a long time, computer scientists considered linear-time algorithms to be the ideal and ultimate goal of any research direction. However, as data sets become larger, it is reasonable and useful to ask if one can non-trivially solve computational tasks using a sublinear amount of resources, such as running time, space, samples, or number of measurements of some kind. Surprisingly, even with sublinear resources one can design non-trivial and meaningful algorithms. In this course, we will learn how to design and analyze sublinear algorithms. Regarding space, we will focus on streaming algorithms, regarding time, we will see property testing, and regarding measurements/samples, we will study sparse vector reconstruction and sparse Fourier transform. We will also consider the connections to classic algorithms, meaning how sublinear algorithms are used as subroutines in classic efficient algorithms.

Tentative Schedule

Date	Topic
07.05.	Introduction (overview, probability background) + Streaming I
11.05.	Tutorial 1 (presence exercises)
14.05.	Streaming II: distinct elements
18.05.	Streaming III: AMS Sketch
21.05.	Holiday
25.05.	Tutorial 2
28.05.	Cancelled due to technical problems
04.06.	Measurements I: Combinatorial group testing ("the syphilis problem"), disjunct and list-disjunct matrices
08.06.	Measurements II: Sparse vector reconstruction, deterministic and randomized algorithms
11.06.	Holiday
15.06.	Tutorial 3
18.06.	Measurements III: Sparse Fourier Transform
22.06.	Property Testing I: Testing monotonicity and linearity
25.06.	Property Testing II: Testing graph properties
29.06.	Tutorial 4
02.07.	Applications I: (Randomized) Sparse Convolution
06.07.	Applications II: Modular Subset Sum from sparse convolution
09.07.	Applications III: String Algorithms
13.07.	Tutorial 5
16.07.	free slot in case of further technical problems