论文标题
连通性的紧密分布素描下限
Tight Distributed Sketching Lower Bound for Connectivity
论文作者
论文摘要
在本文中，我们研究了连通性的分布式草图复杂性。在分布式图素描中，将$ n $ node图$ g $分配给$ n $播放器，使每个播放器都看到一个顶点的附近。然后，玩家同时向裁判发送一条消息，后者必须以高概率计算$ g $的某些功能。对于连通性，裁判是否必须输出$ g $是否连接。目标是最大程度地减少消息长度。这样的草图方案等于广播拥堵集团模型中的单轮协议。 我们证明，如果错误概率最多为$ 1/4 $，则预期的平均消息长度必须至少为$ω（\ log^3 n）$位。它与AGM草图[AGM12]获得的上限匹配，该范围甚至允许裁判输出$ G $的跨越森林，概率$ 1-1/\ mathrm {poly} \，n $。我们的下限增强了以前的$ω（\ log^3 n）$下限用于跨越森林计算[NY19]。因此，这意味着一个决策问题的连接性与此模型中的“搜索”版本一样困难。
In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an $n$-node graph $G$ is distributed to $n$ players such that each player sees the neighborhood of one vertex. The players then simultaneously send one message to the referee, who must compute some function of $G$ with high probability. For connectivity, the referee must output whether $G$ is connected. The goal is to minimize the message lengths. Such sketching schemes are equivalent to one-round protocols in the broadcast congested clique model. We prove that the expected average message length must be at least $Ω(\log^3 n)$ bits, if the error probability is at most $1/4$. It matches the upper bound obtained by the AGM sketch [AGM12], which even allows the referee to output a spanning forest of $G$ with probability $1-1/\mathrm{poly}\, n$. Our lower bound strengthens the previous $Ω(\log^3 n)$ lower bound for spanning forest computation [NY19]. Hence, it implies that connectivity, a decision problem, is as hard as its "search" version in this model.
