A distance oracle for a graph $G = (V, E)$ is a data structure that enables fast retrieval of approximate distances between any pair of query vertices. The oracle has a stretch of $(\alpha, \beta)$ if the estimated distance $\hat{d}(x, y)$ for any $x,y\in V$ satisfies the inequality:
$$d(x, y) \leq \hat{d}(x, y) \leq \alpha \cdot d(x, y) + \beta, ~ \forall x, y \in V.$$
In the fault-tolerant model, a related well-studied problem is the distance sensitivity oracle (DSO). Here, given a query vertex pair $(s, t)$ and a set $F$ of failed edges, the goal is to efficiently approximate the distance between $s$ and $t$ in the graph $G - F$. Over the past two decades, significant efforts have been made to design compact distance oracles for both static and fault-prone graphs.
In this talk, I will discuss the following results:
1. The first static distance oracle with subquadratic space and sublinear query time that achieves a stretch of $(1 + \epsilon, O(1))$, where $\epsilon > 0$ is a small constant.
2. The first $f$-fault-tolerant DSO with subquadratic space and constant stretch, independent of $f$.
Short Bio:
Keerti Choudhary is an Assistant Professor in the Department of Computer Science and Engineering at IIT Delhi. Prior to this, she held post-doctoral positions at Tel Aviv University and the Weizmann Institute of Science. She earned her Ph.D. in Computer Science and an Integrated M.Sc. in Mathematics from IIT Kanpur. Her research interests lie in graph theory, fault-tolerant structures, and dynamic graph algorithms.
