Ariel Korin

Hardness Results for Approximate Distance Labeling in Sparse Graphs

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uzna\'nski, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index c...