Difference between revisions of "Open Problems:65"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
 
(4 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Communication Complexity of Connectivity
 
 
|source=bertinoro14
 
|source=bertinoro14
 
|who=Andrew McGregor
 
|who=Andrew McGregor
 
}}
 
}}
In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $\log^3n$-sized sketch describing its neighborhood, and sends it to a controller. Each node has access to a public shared random source to compute this sketch.
+
A recent result in graph sketching {{cite|AhnGM-12}} can be rephrased in terms of a simultaneous message communication protocol with public coins. Specifically, suppose that $n$ players are each given a row of the adjacency matrix of some graph. The players simultaneously send a message to a central player who must then determine whether the graph is connected. Existing work shows that this is possible with $O(\log^3 n)$ bit messages from each player. Are $O(\log^2 n)$ or $O(\log n)$ bits sufficient? Also, is there a non-trivial lower bound if the players must use private coins?
  
Can we reduce the number of bits required by each node ? To $\log^2 n$ ? To $\log n$ ?
+
== Update ==
 +
The conjecture has been resolved by Yu {{cite|Yu-21}}.

Latest revision as of 16:28, 16 June 2022

Suggested by Andrew McGregor
Source Bertinoro 2014
Short link https://sublinear.info/65

A recent result in graph sketching [AhnGM-12] can be rephrased in terms of a simultaneous message communication protocol with public coins. Specifically, suppose that $n$ players are each given a row of the adjacency matrix of some graph. The players simultaneously send a message to a central player who must then determine whether the graph is connected. Existing work shows that this is possible with $O(\log^3 n)$ bit messages from each player. Are $O(\log^2 n)$ or $O(\log n)$ bits sufficient? Also, is there a non-trivial lower bound if the players must use private coins?

Update[edit]

The conjecture has been resolved by Yu [Yu-21].