Theory Lunch Seminar - Yaowei Long

— 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
YAOWEI LONG, Ph.D. Student, Computer Science and Engineering Division, University of Michigan
https://longyaowei.github.io/

We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query   |F| ≤ f, we can determine whether s and t are still connected in G — F, given only the labels of F ⊂ {s,t}. This problem has been considered when F ⊂ E (edge faults) and F ⊂ V (vertex faults), where correctness is guaranteed with high probability (w.h.p.) or deterministically. In this talk, I will introduce a new deterministic labeling scheme for edge faults that uses Õ(√ f¯ )-bit labels, which can be constructed in polynomial time. This improves on Dory and Parter's [PODC 2021] existential bound of O(f log n) (requiring exponential time to compute) and the efficient Õ(f2)-bit scheme of Izumi, Emek, Wadayama, and Masuzawa [PODC 2023]. Our construction uses an improved edge-expander hierarchy and a distributed coding technique based on Reed-Solomon codes. 

Based on joint work  with Seth Pettie and Thatchaphol Saranurak.

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250312.html

Add event to Google
Add event to iCal