Networks and Distributed Computing Series
Universal Communication, Universal Graphs, and Graph Labeling
14th January 2021, 15:30
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
Additional Materials
Maintained by Giorgos Christodoulou