Sublinear Algorithms

Advanced Course

Postponed by 4 weeks!

Please note that on 11.3., the entire Saarland university has postponed the start of the semester by 4 weeks.  This also affects this course.  We will update the information below as soon as we can.

Basic Information

Lectures:Thursday, 16:15 - 18:00, E1.4 024
Lecturer:Karl Bringmann, Vasileios Nakos
First lecture:TBA
Tutorials:every second Monday, 16:15 - 18:00, E1.4 024
Assistant:Nick Fischer
First tutorial:TBA
Credits:5
Exam:Oral Exam
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

  • The course will most likely be virtual. Lectures and tutorials will be given on standard teleconference systems such as Zoom.

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

DateTopicDiscussed
07.04Introduction: sparse recovery problem, probability and algorithms background
14.04Streaming I: Approximate counting (Morris algorithm)
21.04Streaming II: AMS Sketch
28.04

Streaming III: Necessity of randomization and approximation in streaming algorithms

05.05Measurements I: Combinatorial group testing ( "the syphilis problem"): disjunct
and list-disjunct matrices
12.05

Measurements II: Sparse vector reconstruction,
deterministic and randomized algorithms

19.05Measurements III: (Randomized) Sparse Convolution
26.05Measurements IV: Introduction to the Sparse Fourier Transform problem
02.06Measurements V: Sparse Fourier Transform via Filter-based Sampling
09.06Property Testing I: Testing monotonicity and linearity
16.06Property Testing II: Testing graph properties
30.06Applications I: Modular Subset Sum from sparse convolution
07.07Applications II: Subset Sum and Prefix-restricted Sumset Computation
14.07Applications III: String Algorithms
  
   

Material

TBA