Events Calendar

Shiri Chechik (Microsoft Research) Distance Oracles with Local Stretch

Speaker: Shiri Chechik , Microsoft Research Silicon Valley

Talk Title: Distance Oracles with Local Stretch

Series: USC CS Theory

Abstract: A Distance Oracle is a succinct data structure that provides fast answers to distance queries between any two points.
Distance oracles are measured by several parameters: construction time (the running time of the algorithm to produce the data structure), size (the worst case size of the data structure), query complexity (the running time of the query algorithm, given two points), and stretch guarantee (the maximum ratio between the estimated distance returned by the distance oracle and the actual distance).
In this talk we will consider a more refined local stretch guarantee first suggested by Abraham, Bartal and Neiman [STOC 07]. Informally, we wish to obtain better stretch guarantees for nearby pairs. We would like the stretch bound to gradually improve as we query closer pairs of points.

We consider two notions of local stretch for distance oracles:
1. Strong local stretch provides stretch guarantees for any pair of nodes with better stretch guarantees for nearby pairs.
2. Weak local stretch provides stretch guarantees only between pair of nodes u and v, such that v is in the r-neighborhood of u (v is one of the r’th closest nodes to u), for some parameter r.

We will discuss these two notions and see efficient constructions for both these notions improving upon previous work.

Based on a joint work with Ittai Abraham

Biography: Shiri Chechik is Postdoctoral Researcher at Microsoft Research Silicon Valley. She recently completed her PhD under the supervision of Prof. David Peleg in the Weizmann Institute of Science in Israel.
She is interested in Theoretical Computer Science, with an emphasis on Design and Analysis of Algorithms for network problems.
Home page: http://research.microsoft.com/en-us/people/schechik/.

Host:

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Assistant to CS chair