License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.33
URN: urn:nbn:de:0030-drops-117182
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11718/
Go to the corresponding LIPIcs Volume Portal

Harms, Nathaniel

Universal Communication, Universal Graphs, and Graph Labeling

pdf-format:
LIPIcs-ITCS-2020-33.pdf (0.6 MB)

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 k-Hamming 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 super-constant Ω(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, low-arboricity graphs, and planar graphs, admit constant-cost 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:1--33:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11718},
  URN =		{urn:nbn:de:0030-drops-117182},
  doi =		{10.4230/LIPIcs.ITCS.2020.33},
  annote =	{Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance}
}

Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI