Registration for this course is open until Wednesday, 17.01.2024 23:59.


Today's Tutorial

Written on 30.11.23 by Alejandro Cassis

Dear all,

As per your requests, starting from today we will start the tutorials at 16:15.

Exercise Sheet 4

Written on 29.11.23 by Alejandro Cassis

Hi everyone,

Exercise sheet 04 has been released.

Exercise 3

Written on 15.11.23 by Nithin Varma

Dear all,

Exercise sheet 3 has been released. Apologies for the delay.

Mistake in Exercise 2.2

Written on 03.11.23 by Alejandro Cassis

Dear all,

We realized we had a mistake in exercise 2.2 of Sheet 02. The intended running time is O(m + n log(n)). The correct pdf is updated in the CMS.

Sorry for the inconvenience.

Tutorial Information

Written on 02.11.23 by Alejandro Cassis

Dear all,

Today's tutorial is at 10:15 in room 024 E1 4.

As agreed in the last lecture, starting from the next tutorial (on 16.11) we will change the time to 16:00, in the same room.

Primer to Randomness

Written on 14.10.23 by Karl Bringmann

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 under Information->Materials->Further Reading. We suggest that you read at least the first half of… Read more

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 under Information->Materials->Further Reading. We suggest that you read at least the first half of this document before the first lecture, Section 3 before the second lecture, and the whole document at the latest before the third lecture.

Show all

Sublinear Algorithms

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 solve computational tasks using a sublinear amount of resources, such as running time or space. 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, and regarding time we will focus on property testing. We will also consider applications of sublinear algorithms in classic algorithm design, that is, how sublinear algorithms are used as subroutines in classic efficient algorithms.

Time, Date, and Format

This course consists of one lecture per week (Tuesday 16:00-18:00) and a tutorial every other week (Thursday 10:15-12:00). See Information->Timetable for details.

The first lecture is on October 24. The first tutorials is held on October 26. Lectures and tutorials are held physically in room 024 building E1 4.


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 "Introduction to Algorithms and Data Structures". The core lecture "Algorithms and Data Structures" would be helpful, but is not a formal requirement.


You need to register on this webpage to get access to exercise sheets and other course material.


An important part of the course are the exercises, where you will analyze and design sublinear algorithms on your own. Solutions to the exercise sheets are due at the beginning of the lecture, and can be submitted either on paper in the lecture on virtually on this website. There will be 7 exercise sheets. You are allowed to collaborate on the exercise sheets, but you have to write down a solution on your own, using your own words. Please indicate the names of your collaborators for each exercise you solve. Further, cite all external sources that you use (books, websites, research papers, etc.). If you use any AI tools such as ChatGPT, explicitly mention this use as part of your solution and describe in 1-3 lines how you used it.


To be admitted to the exam, you need to score at least 50% of the points on the exercise sheets. Your grade will be determined by a written or oral exam.

Tentative Schedule

This is a tentative list of topics.

Date Lecturer Topic Comment
24.10. 4pm KB Introduction (overview, probability background) + Streaming I: Morris counter  
26.10. 10am AC Tutorial 0 (more probability background, presence exercises)  
31.10. 4pm KB Streaming II: distinct elements + Applications I: reachability counting  
2.11. 10am AC Tutorial 1  
7.11. 4pm KB Streaming III: moment estimation (AMS sketch), heavy hitters (CountMin sketch)  
14.11. 4pm NV Streaming IV: L0 sampling, graph streams, linear sketching for connected components  
16.11. 10am HA Tutorial 2  
21.11. 4pm NV Property Testing I: sortedness of lists, monotonicity of functions  
28.11. 4pm KB Streaming V: sparse recovery  
30.11. 10am AC Tutorial 3  
5.12. 4pm NV Property Testing II: linearity of Boolean functions  
12.12. 4pm NV Property Testing III: graph properties: connectedness of sparse graphs, bipartiteness of dense graphs  
14.12. 10am AC Tutorial 4  
19.12. 4pm KB Applications II: sparse matrix multiplication and sparse convolution  
2.1. 4pm NV Sampling: generating a uniformly random edge in streaming and query models  
9.1. 4pm KB Property Testing IV: estimating the edit distance between strings  
11.1. 10am HA Tutorial 5  
16.1. 4pm NV Property Testing V: estimating the weight of Euclidean Minimum Spanning Tree  
23.1. 4pm NV Lower Bounds I: Yao’s principle and applications  
25.1. 10am HA Tutorial 6  
30.1. 4pm NV Lower Bounds II: Communication complexity and applications  
6.2. 4pm   Outlook  
8.2. 10am HA Tutorial 7  


The course will not follow a particular book. Some references can be found under Information->Material.

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.