Seminar Distance Oracles

» Diese Veranstaltung wird auf englisch gehalten.

Content

Distance oracles are data structures for the following problem: We are given a description of a large network, for example a roadmap. Each link in the network has a length associated with it. We want to built a data structure that allows us to answer distance queries ("How long does it take me to get from point A to point B in the network?") and shortest pathz queries ("What's the best way to get from A to B?") as efficiently as possible, using as little space as possible to store the data structure. There has been a wealth of research on this problem that provides deep and surprising solutions.

In this seminar, we are going to study distance oracles and related data structures such as spanners and neighbourhood covers. These data structures have numerous applications, in particular in mobile and distibuted computing, yet at the same time their construction touches upon foundational questions in graph theory.

Organization

The seminar is organized by Prof. Martin Grohe.

The seminar will be held in English.

The presentations are given weekly in blocks of two talks on Thursday from 1pm-3pm, starting in the second half of the semester (the exact starting state depends on the number of participants).

This seminar is on theoretical computer science. A good knowledge from the basic theory courses is expected.