April 24th, Wednesday 14:15, Room 303, Jacobs Building

Title: Distance oracles

Lecturer: Liam Roditty

Lecturer homepage : http://u.cs.biu.ac.il/~liamr/

Affiliation : Department of Computer Science Bar-Ilan University

Computing distances is one of the most fundamental computational problems. In many applications we are not really interested in all distances, we want the ability to retrieve them quickly. Thorup and Zwick (2005) initiated the theoretical study of data structures capable of representing approximated distances efficiently, in terms of space requirement and query time. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k = 1 it is possible to preprocess the graph in T(mn^{1/k}) time and generate a compact data structure of size O(n^{1+1/k}). For each pair of vertices, it is then possible to retrieve a stretch k approximate distance in O(k) time. Recently, Patrascu and Roditty (2010) broke the long-standing theoretical status-quo in the field of distance oracles. They obtained, in particular, a distance oracle for unweighted graphs of size O(n^{5/3}) that can supply in O(1) time an estimated distance in the range [d,2d+1], where d is the actual distance between the two vertices queried. In FOCS'12 Patrascu, Roditty and Thorup extended this result to a new infinity of space stretch trade-off values. In the talk I will discuss these recent developments.