论文标题
超越爱丽丝和鲍勃：提高了最大独立设置的不易Xibibibibibility in Excest
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
论文作者
论文摘要
到目前为止，最富有成果的技术用于交通拥堵模型的下限是降低两方通信复杂性。对于各种基本问题，例如距离计算，最小跨越树，最小顶点覆盖物等，该技术几乎取得了紧张的结果。 在这项工作中，我们将此技术进一步发展，并为每$ t \ geq 2 $介绍了一个减少到$ t $ - 部分通信复杂性的框架。我们的框架使我们能够显示出最大独立集的硬度结果。最近，Bachrach等人[PODC 2019]使用了两党框架来显示近似的硬度，以实现最大独立集。他们表明，找到$（5/6+ε）$ - 近似需要$ω（n/\ log^6 n）$ rounds，找到$（7/8+ε）$ - 近似需要$ω（n^2/\ log^7 n）$ younds，在网络中的nodes nodes中的$ n $ n $ n。 我们改善了Bachrach等人的结果。通过减少多方交流复杂性。我们的结果： （1）任何发现$（1/2+ε）$的算法 - 在拥塞模型中最大独立设置的近似值需要$ω（n/\ log^3 n）$ rounds。 （2）任何发现$（3/4+ε）$ - 最大独立集合中的近似近似的任何算法都需要$ω（n^2/\ log^3 n）$ rounds。
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight results for various fundamental problems such as distance computations, minimum spanning tree, minimum vertex cover, and more. In this work, we take this technique a step further, and we introduce a framework of reductions to $t$-party communication complexity, for every $t\geq 2$. Our framework enables us to show improved hardness results for maximum independent set. Recently, Bachrach et al.[PODC 2019] used the two-party framework to show hardness of approximation for maximum independent set. They show that finding a $(5/6+ε)$-approximation requires $Ω(n/\log^6 n)$ rounds, and finding a $(7/8+ε)$-approximation requires $Ω(n^2/\log^7 n)$ rounds, in the CONGEST model where $n$ in the number of nodes in the network. We improve the results of Bachrach et al. by using reductions to multi-party communication complexity. Our results: (1) Any algorithm that finds a $(1/2+ε)$-approximation for maximum independent set in the CONGEST model requires $Ω(n/\log^3 n)$ rounds. (2) Any algorithm that finds a $(3/4+ε)$-approximation for maximum independent set in the CONGEST model requires $Ω(n^2/\log^3 n)$ rounds.
