Exercise Sheet 7 is out now

Written on 24.01.24 by Karl Bringmann

As usual you can find it on the Material page of this website. Sorry for the delay.

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 exam. Your final grade will be the better of your grade in the final exam and your grade in the re-exam. For passing the course it suffices to pass one of the exams, so it is not necessary to participate in both exams (but can be beneficial to improve your grade). For the exams you are allowed to bring a single one-sided handwritten DinA4-sheet; photocopies and printouts are not allowed.

Final exam: February 13, 2pm-4pm, HS001 in E1 3, please arrive 10min before 2pm

Re-exam: March 27, 2pm-4pm, HS001 in E1 3, please arrive 10min before 2pm

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, number of connected components  
14.12. 4pm AC Tutorial 4  
19.12. 4pm KB Applications II: sparse matrix multiplication and sparse convolution  
2.1. 4pm   canceled  
9.1. 4pm NV Property Testing IV: distribution testing  
16.1. 4pm KB Lower Bounds I: encoding arguments  
18.1. 4pm HA Tutorial 5  
23.1. 4pm KB Lower Bounds II: communication complexity  
25.1. 4pm HA Tutorial 6  
30.1. 4pm NV Property Testing V: Lower Bounds using Yao's principle  
6.2. 4pm NV Outlook + Sampling: generating a uniformly random edge in streaming and query models  
8.2. 4pm 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.