Distributed connectivity and the k-out random graph conjecture

25^th November 2021, 16:00
Valerie King
University of Victoria, Canada

Abstract

We 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.

This is joint work with Jacob Holm, Mikkel Thorup, Or Zamir, and Uri Zwick which appeared in FOCS 2019.