Theory Seminar, Wednesday June 10: Gur Lifshitz (TAU) - (α,β)-Spanners and Hybrid Spanners with Nearly Tight Bounds
1 view
Skip to first unread message
Arnold Filtser
Jun 3, 2026, 12:00:23 AMJun 3
to BIU Theory Seminar, Gur Lifshitz
Hi all,
Today (Wednesday June 3) there is no theory seminar.
Next week (Wednesday June 10, at 12pm) we will meet for our theory seminar.
Location: Building 503 room 226.
Looking forward to seeing you all there,
Arnold
Speaker: Gur Lifshitz (TAU)
Title: (α,β)-Spanners and Hybrid Spanners with Nearly Tight Bounds
Abstract: An (α,β)-spanner of an n-vertex undirected, unweighted graph G is a subgraph H satisfying
dist_H(u,v)≤ α dist_G(u,v) + β for all u,v.
Classical results give (2k−1,0)-spanners with O(n^{1+1/k}) edges, and, assuming Erdős’ girth conjecture, this is optimal for preserving distances of adjacent pairs. However, this lower bound does not rule out better guarantees for vertices whose original distance is larger.
I will present new constructions that achieve nearly optimal stretch for every distance d ≤ k. We build a spanner with |E(H)| = O(n^{1+1/k} + d log(dn)) edges such that all pairs at distance at most d in G satisfy dist_H(u,v)≤2k+O(d logd). Equivalently, the multiplicative stretch for distance-d pairs is 2k/d+O(logd).
As a concrete consequence, setting d=k/log k yields an (O(log k),O(k))-spanner with O(n^{1+1/k}+kn) edges. For comparison, Ben-Levy and Parter (SODA 2020) obtained $(O(k^ε),O(k))$-spanners, where the size dependence deteriorates rapidly as ε decreases. Our result improves the multiplicative stretch from k^ε down to logk, moving substantially closer to the long-standing goal of constructing (O(1),O(k))-spanners.
Joint work with Shiri Schechik. Appeared in SODA 2026.
Title: (α,β)-Spanners and Hybrid Spanners with Nearly Tight Bounds
Abstract: An (α,β)-spanner of an n-vertex undirected, unweighted graph G is a subgraph H satisfying
dist_H(u,v)≤ α dist_G(u,v) + β for all u,v.
Classical results give (2k−1,0)-spanners with O(n^{1+1/k}) edges, and, assuming Erdős’ girth conjecture, this is optimal for preserving distances of adjacent pairs. However, this lower bound does not rule out better guarantees for vertices whose original distance is larger.
I will present new constructions that achieve nearly optimal stretch for every distance d ≤ k. We build a spanner with |E(H)| = O(n^{1+1/k} + d log(dn)) edges such that all pairs at distance at most d in G satisfy dist_H(u,v)≤2k+O(d logd). Equivalently, the multiplicative stretch for distance-d pairs is 2k/d+O(logd).
As a concrete consequence, setting d=k/log k yields an (O(log k),O(k))-spanner with O(n^{1+1/k}+kn) edges. For comparison, Ben-Levy and Parter (SODA 2020) obtained $(O(k^ε),O(k))$-spanners, where the size dependence deteriorates rapidly as ε decreases. Our result improves the multiplicative stretch from k^ε down to logk, moving substantially closer to the long-standing goal of constructing (O(1),O(k))-spanners.
Joint work with Shiri Schechik. Appeared in SODA 2026.
Arnold Filtser
Jun 10, 2026, 2:01:46 AMJun 10
to BIU Theory Seminar, Gur Lifshitz
Reminder, the seminar will start in 3 hours!
Reply all
Reply to author
Forward
0 new messages