Harms, Nathaniel
Universal Communication, Universal Graphs, and Graph Labeling
Abstract
We introduce a communication model called universal SMP, in which Alice and Bob receive a function f belonging to a family ℱ, 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 of universal SMP 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 x and y can be determined from the labels ℓ(x), ℓ(y). We give a universal SMP protocol using O(k^2) bits of communication for deciding whether two vertices have distance at most k in distributive lattices (generalizing the kHamming Distance problem in communication complexity), and explain how this implies a O(k^2 log n) labeling scheme for deciding dist(x,y) ≤ k on distributive lattices with size n; in contrast, we show that a universal SMP protocol for determining dist(x,y) ≤ 2 in modular lattices (a superset of distributive lattices) has superconstant Ω(n^{1/4}) communication cost. On the other hand, we demonstrate that many graph families known to have efficient adjacency labeling schemes, such as trees, lowarboricity graphs, and planar graphs, admit constantcost communication protocols for adjacency. Trees also have an O(k) protocol for deciding dist(x,y) ≤ k and planar graphs have an O(1) protocol for dist(x,y) ≤ 2, which implies a new O(log n) labeling scheme for the same problem on planar graphs.
BibTeX  Entry
@InProceedings{harms:LIPIcs:2020:11718,
author = {Nathaniel Harms},
title = {{Universal Communication, Universal Graphs, and Graph Labeling}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {33:133:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11718},
URN = {urn:nbn:de:0030drops117182},
doi = {10.4230/LIPIcs.ITCS.2020.33},
annote = {Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance}
}
06.01.2020
Keywords: 

Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 