# 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

Date | Topic | Discussed |
---|---|---|

07.04 | Introduction: sparse recovery problem, probability and algorithms background | — |

14.04 | Streaming I: Approximate counting (Morris algorithm) | — |

21.04 | Streaming II: AMS Sketch | — |

28.04 | Streaming III: Necessity of randomization and approximation in streaming algorithms | — |

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

12.05 | Measurements II: Sparse vector reconstruction, | — |

19.05 | Measurements III: (Randomized) Sparse Convolution | — |

26.05 | Measurements IV: Introduction to the Sparse Fourier Transform problem | — |

02.06 | Measurements V: Sparse Fourier Transform via Filter-based Sampling | — |

09.06 | Property Testing I: Testing monotonicity and linearity | — |

16.06 | Property Testing II: Testing graph properties | — |

30.06 | Applications I: Modular Subset Sum from sparse convolution | — |

07.07 | Applications II: Subset Sum and Prefix-restricted Sumset Computation | — |

14.07 | Applications III: String Algorithms | — |

— | ||

# Material

TBA