Sketching Distances in Monotone Graph Classes

Louis Esperet, Nathaniel Harms, Andrey Kupavskii

We study the two-player communication problem of determining whether two vertices $x,y$ are nearby in a graph $G$, with the goal of determining the graph structures that allow the…