The Taub Faculty of Computer Science Events and Talks

Theory Seminar: An f-edge fault-tolerant distance sensitivity oracle (f-DSO) is a data-structure that, when queried with two vertices (s, t) and a set F of at most f edges of a graph G with n vertices, returns an estimate tilde{d}(s,t,F) of the distance d(s,t,F) from s to t in G – F. The oracle has stretch alpha if the estimate satisfies d(s,t,F) le tilde{d}(s,t,F) le alpha cdot d(s,t,F) . In the last two decades, extensive research has focused on developing efficient f-DSOs. This research aims to optimize preprocessing time, space consumption, and query time, as well as to improve the stretch (approximation guarantee). Efforts have also been made to derandomize the construction and query algorithms of these systems. Over the last two decades, extensive research has been conducted on developing efficient f-DSOs. This research has focused on optimizing various aspects such as preprocessing time, space consumption, query time, and stretch (approximation guarantee). Efforts have also been made to derandomize the construction algorithms of these data-structures. While multiple constructions of f-DSOs are already known, surprisingly, there is still no optimal data-structure that supports multiple failures. In this talk, we will cover several recent f-DSO data-structures and discuss open questions in this field.