Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Distance Sensitivity Oracles
event speaker icon
Sarel Cohen (Tel-Aviv Academic College)
event date icon
Wednesday, 28.02.2024, 12:15
event location icon
Taub 201
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.