# 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 |

# Exercises

Exercise Sheet 0 (presence exercises)