Nathan
Harms,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We introduce a communication model called Universal SMP, in which Alice and Bob receive a function f belonging to a family F, and inputs x and y. Alice and Bob use shared randomness to send a message to a third party who cannot see f, x, y, or the shared randomness, and must decide f(x,y).
Our main application is to relate communication complexity to graph labeling, where the goal is to give a short label to each vertex in a graph, so that adjacency or other functions of two vertices and can be determined from the labels. We give a universal SMP protocol for deciding dist(x,y) < k in distributive lattices, with cost independent of the lattice size, and explain how this implies a labeling scheme.
We demonstrate that many graph families known to have efficient labeling schemes also admit constant-cost communication protocols, such as trees, low-arboricity graphs, and planar graphs. We also give protocols for deciding dist(x,y) < k in trees and dist(x,y) <= 2 in planar graphs, which implies a new labeling scheme for planar graphs.