#### Theory Seminar

# Zihan Tan: Almost-Optimal Sublinear Additive Spanners

WHERE:

3725 Beyster Building

WHEN:

Friday, April 14, 2023 @ 3:00 pm - 4:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

SHARE:

Given an undirected unweighted graph G=(V, E) on n vertices and m edges, a subgraph H is a spanner of G with stretch function f, iff for every pair s, t of vertices, dist_H(s,t) is at most f(dist_G(s,t)). When f(d)=d+o(d), H is called a sublinear additive spanner. In this talk, we show that for any constant integer k>=2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^{1-1/k}) and O(n^{1+1/(2^{k+1}-1)+o(1)}) edges. The size bound of our spanners almost matches the lower bound proved in [Abboud-Bodwin-Pettie 2017], which holds for any data structure that maintains distances within the same stretch function.

This talk is based on joint work with Tianyi Zhang.