论文标题
确定性的近距离分布式列表
Deterministic Near-Optimal Distributed Listing of Cliques
论文作者
论文摘要
在大图中分类连接的重要性是在分布式子图发现上进行丰富工作的动机，这导致了最近的突破。保持开放的一个关键方面是确定性算法是否可以像随机算法一样有效，而后者已知对多毛体因子紧密。 我们提供了确定性分布式算法，用于列出$ n^{1-2/p + o（1）} $ roughs y \ colest型号中的$ p $ $ p $的集团。对于三角形，我们的$ n^{1/3+o（1）} $圆形复杂性在先前的$ n^{2/3+o（1）} $ rounds的艺术状态下有所改善[Chang and Saranurak，focs 2020]。对于大小$ p \ geq 4 $的集团，我们的是第一个非平凡的确定性分布式算法。给定已知的下限，对于所有值$ p \ geq 3 $，我们的算法紧密至$ n^{o（1）} $ sublynomial因子，这来自我们使用的确定性路由过程。
The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size $p$ in $n^{1 - 2/p + o(1)}$ rounds in the \congest model. For triangles, our $n^{1/3+o(1)}$ round complexity improves upon the previous state of the art of $n^{2/3+o(1)}$ rounds [Chang and Saranurak, FOCS 2020]. For cliques of size $p \geq 4$, ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values $p \geq 3$ our algorithms are tight up to a $n^{o(1)}$ subpolynomial factor, which comes from the deterministic routing procedure we use.
