Geometric algorithms with limited resources

Advanced Course, 2+1

Basic Information

Lectures:Tuesday 10:00-12:00 Location: Zoom, https://cs-uni-saarland-de.zoom.us/j/91928115054
Lecturers:Themistoklis Gouleakis and Sándor Kisfaludi-Bak
First lecture:13.04.2021, 10:00 am
Tutorials:Friday 10:00
Teaching Assistant:Hannaneh Akrami
First tutorial:16.04.2021, 10:00 am
Credits:5
Exam:Oral
Prerequisites:Basics of data structures, algorithms, linear algebra, probability

Announcements

All students should subscribe to the following mailing list:

https://lists.mpi-inf.mpg.de/listinfo/geoalgolr

The course will be held in the following Zoom room:
https://cs-uni-saarland-de.zoom.us/j/91928115054

If you still need the password for the Zoom room, please send one of the lecturers an email.

Description

Spatial data arises in several settings: it may come directly from geometic data (such as GPS coordinates, pixels and their locations in a digital picture, or voxels in a brain scan), but it is also often useful to regard any data as a point set in high-dimensional space. The goal of the course is to look at algorithms that are able to process such data even with very limited resources, e.g. using very limited (sublinear) computation time or space. We will look at several types of resource restrictions, such as property testing, sublinear algorithms, constant workspace algorithms, and the usual algorithmic design techniques used in these settings. These allow one to make useful inferences from spatial data even with very limited resources.

 

 

Join the course mailing list here: https://lists.mpi-inf.mpg.de/listinfo/geoalgolr

 

Schedule

DateTopicLecturer/TutorSlides/Assignment
13.04Introduction, concepts from computational geometrySándor Kisfaludi-Bakpdf
20.04Introdcution to sublinear algroithmsThemistoklis Gouleakis 
27.04Property testing in Eudlidean spaceSándor Kisfaludi-Bak 
04.05Sublinear algorithms in metric spacesThemistoklis Gouleakis