Theory Seminar, Wednesday Dec 14: Itai Boneh (Reichman and Haifa) - Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs

[Arnold Filtser]

Hi all,

Next week (Wed Dec 11, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Itai Boneh (Reichman and Haifa)
Title: Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs.
Abstract: We present a labeling scheme that assigns labels of size Õ(1) to the vertices of a directed weighted planar graph G, such that for any fixed ϵ>0 from the labels of any three vertices s, t and f one can determine in Õ(1) time a (1+ϵ)-approximation of the s-to-t distance in the graph G \ {f}.
For approximate distance queries, prior to our work, no efficient solution existed, not even in the centralized oracle setting.
Even for the easier case of reachability, Õ(1) queries were known only with a centralized oracle of size Õ(n) [SODA 21].

Joint work with Shay Golan, Shay Mozes, and Oren Weimann.

[Arnold Filtser]

This happens tomorrow!

[Arnold Filtser]

Please disregard the last email, it was sent by mistake.

The seminar happens on Wednesday the 14 as published.

[Arnold Filtser]

I mean Wed the 11th.