BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260526T000901Z
UID:Seminar-networks-976@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20210114T153000
DTEND:20210114T163000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION: Nathan Harms: Universal Communication, Universal Graphs, and Graph Labeling\n\nIn 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.\n\n\n\nMeeting zoom link: https://liverpool-ac-uk.zoom.us/j/93623403274?pwd=MnRjT3pxNVg4Sm5hRlE3V0hNWVRRUT09\n\n\n\n\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=976
LOCATION:
END:VEVENT
END:VCALENDAR