7 papers
Roundtrip All-Pairs Shortest Paths in Directed Graphs
Shiri Chechik, Gur Lifshitz
We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinar…
Optimal (Randomized) Compact Routing Schemes
Shiri Chechik, Avi Kadria, Gur Lifshitz +1
Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing…
Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners
Shiri Chechik, Gur Lifshitz
In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to trees in expectati…
Reading between the levels: new tools for the Thorup-Zwick hierarchy and their applications
Shiri Chechik, Gur Lifshitz, Avi Kadria +1
In this paper, we develop three new analytical tools for the Thorup-Zwick hierarchy: the Mixed-Level Growth, Two-Level Growth, and Long-Short Growth lemmas. Using these tools, we o…
Spanners and Hybrid Spanners with Nearly Tight Bounds
Shiri Chechik, Gur Lifshitz
For an -vertex undirected, unweighted graph and a positive integer , we present new spanner constructions with edges that achieve nearly optimal gu…
Girth Approximations in the CONGEST Model
Shiri Chechik, Gur Lifshitz, Doron Mukhtar
This paper advances the state of the art in girth approximation within the CONGEST model. Manoharan and Ramachandran [PODC '24] provided the first significant improvement in girth…
Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz +1
Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One po…