Difference between revisions of "Open Problems:65"
(Created page with "{{Header |title=Communication Complexity of Connectivity |source=bertinoro14 |who=Andrew McGregor }} ???") |
|||
| (5 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=bertinoro14 | |source=bertinoro14 | ||
|who=Andrew McGregor | |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? |
| + | |||
| + | == 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].
