Networks and Distributed Computing Series

Universal Communication, Universal Graphs, and Graph Labeling

14th January 2021, 15:30 add to calender
Nathan Harms
University of Waterloo

Abstract

In communication complexity, the Simultaneous Message Passing (SMP) model is where two parties, Alice and Bob, receive inputs x and y respectively, and each send a single message to a third-party referee, who must compute f(x,y), and the function f is known to all parties. What if the third-party referee does not know the function f? That is, the referee must compute a function known to Alice and Bob but not to themself. To study this generalized problem, we introduce a communication model that we call Universal SMP. We show that Universal SMP also generalizes the problem of graph labeling, establishing a new connection between communication complexity, graph labeling, and universal graphs. Communication complexity is usually studied in the randomized setting, while graph labeling and universal graphs are not; this suggests many questions about randomized graph labeling and probabilistic universal graphs. This talk will discuss some results and questions arising from this connection; for example, an interesting corollary is that some common graph families like trees and planar graphs have constant-size probabilistic universal graphs and constant-size randomized small-distance labeling schemes.

Meeting zoom link: https://liverpool-ac-uk.zoom.us/j/93623403274?pwd=MnRjT3pxNVg4Sm5hRlE3V0hNWVRRUT09



add to calender (including abstract)

Additional Materials