BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T211555Z
UID:Seminar-NESTiD-1143@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20211125T160000
DTEND:20211125T170000
SUMMARY:Durham-Liverpool synergy Series
DESCRIPTION:Valerie King: Distributed connectivity and the k-out random graph conjecture\n\nWe consider the following problem. Each node in a graph has a distinct ID and each knows only the ID’s of its neighbors. Suppose it can send one message to a referee who must determine the graph’s connected components. The graph sketching technique described by Ahn, Guha and McGregor in 2012 gives a method which requires only O(log^3 n) bits to be sent by each node, to compute the solution with high probability, and this is tight, according to a recent result of Nelson and Yu. However this method requires public randomness. We began by investigating the one-way communication cost of this problem when there is private randomness, and ended up posing and partially proving a surprising conjecture about sampling in graphs and connectivity.\n\nThis is joint work with Jacob Holm, Mikkel Thorup, Or Zamir, and Uri Zwick which appeared in FOCS 2019.\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1143
LOCATION:
END:VEVENT
END:VCALENDAR