Sublinear Algorithms

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.

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

Registration

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

Exercises

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.

Exam

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

Literature

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