Seminar Upcoming

The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.

 Wednesdays, 13:00-14:00 (food starts at 12:45)
 Room 201 (note return to traditional room), Taub Building

If you are interested in giving a talk at the seminar, contact Omri Ben-Eliezer and/or David Wajc.

The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.

To join or leave our mailing list.

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs

Wed, July 2

Itai Boneh (Reichman University and University of Haifa)

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 Shiri Chechik, Shay Golan, Shay Mozes, and Oren Weimann.

Ilan Komargodski (Hebrew University)

Wed, July 9

Ilan Komargodski (Hebrew University)