Open Problems:65 - Revision history

98.110.124.189 at 16:28, 16 June 2022

2022-06-16T16:28:41Z

2014-06-13T23:00:39Z

2014-06-13T23:00:22Z

2014-06-13T22:38:42Z

2014-06-04T04:18:28Z

2014-05-28T21:43:43Z

2014-05-28T15:59:39Z

Created page with "{{Header |title=Communication Complexity of Connectivity |source=bertinoro14 |who=Andrew McGregor }} ???"

New page

{{Header
|title=Communication Complexity of Connectivity
|source=bertinoro14
|who=Andrew McGregor
}}
???

← Older revision		Revision as of 16:28, 16 June 2022
Line 4:		Line 4:
	}}		}}
	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?		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?
		+
		+	== Update ==
		+	The conjecture has been resolved by Yu {{cite\|Yu-21}}.

@@ Line 4: / Line 4: @@
 |who=Andrew McGregor
 }}
-In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $O(\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?

@@ Line 4: / Line 4: @@
 |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.
+In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $O(\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.
-Can we reduce the number of bits required by each node ? To $\log^2 n$ ? To $\log n$ ?
+Can we reduce the number of bits required by each node? Can it be made as small a $O(\log^2 n)$ or $O(\log n)$?

@@ Line 4: / Line 4: @@
 |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.

← Older revision	Revision as of 23:00, 13 June 2014
(No difference)

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro14
 |who=Andrew McGregor
 }}
 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?