论文标题
我们可以在一轮拥挤的集团中计算什么？
What Can We Compute in a Single Round of the Congested Clique?
论文作者
论文摘要
我们表明，在最坏情况下，在单播充血集团中计算最小跨越树（MST）的任何单轮算法都必须使用$ω（\ log^3 n）$ bits的链接带宽。因此，根据$ o（\ log n）$ - 大小消息计算MST至少需要$ 2 $。这是单播充血集团中的第一轮复杂性下限，因为问题大小很小，即$ o（n \ log n）$位。只要MST的每个边缘都通过一个入射节点输出，我们的下限将保持。据我们所知，单播充血集团的所有先前的下限都考虑了具有较大输出大小（例如三角列举）的问题，或者要求每个节点学习整个输出。
We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of $Ω(\log^3 n)$ bits in the worst case. Consequently, computing an MST under the standard assumption of $O(\log n)$-size messages requires at least $2$ rounds. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., $O(n\log n)$ bits. Our lower bound holds as long as every edge of the MST is output by an incident node. To the best of our knowledge, all prior lower bounds for the unicast congested clique either considered problems with large output sizes (e.g., triangle enumeration) or required every node to learn the entire output.
