论文标题
概括了lovász局部引理的分布复杂性的尖锐阈值现象
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
论文作者
论文摘要
最近，勃兰特（Brandt），莫斯（Maus）和乌托（Uitto）[PODC'19]表明，在有限的环境中，分布式洛瓦斯兹（Lovász）本地引理（LLL）的复杂性的依赖性依赖于所选的lll标准的复杂性，在每种情况下，如果在每个lll标准$ p2^d <1 $ complects complects complects complects complects complate ll offers complects complate ll the lll the lll temomenon均表现出鲜明的阈值。本地模型为$ O（d^2 + \ log^* n）$。与之形成鲜明对比的是，在标准$ p2^d \ leq 1 $下，布兰特等人的$ω（\ log \ log n）$的随机下限。 [stoc'16]以及Chang，Kopelowitz和Pettie [focs'16]的$ω（\ log n）$的确定性下限。布兰特（Brandt），莫斯（Maus）和乌伊托（Uitto）猜想，对于每个随机变量都会影响许多事件的不受限制设置，相同的行为也是如此。 我们通过提供了一种算法来证明它们的猜想，该算法在LLL标准下解决了时间$ O（D^2 + \ log^* n）$（d^2 + \ log^* n）$，$ p2^d <1 $，由于$ω（\ log^* n）$下by，chung，pettie和su [podtie and su [podc'14]，在界数图中很紧张。通过勃兰特（Brandt），毛斯（Maus）和乌伊托（Uitto）的工作，获得这样的算法可以减少到证明任意高维度中某个功能家族中的所有成员在某些特定领域上都是凸的。不幸的是，对这些功能的分析描述最多仅以$ 3 $而闻名，这导致了上述结果的限制。在获得（基本上）较高维度的功能的这些描述似乎不在当前技术的范围之内，但我们表明它们的凸度可以通过组合手段来推断。
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL criterion exhibits a sharp threshold phenomenon: They proved that, under the LLL criterion $p2^d < 1$, if each random variable affects at most $3$ events, the deterministic complexity of the LLL in the LOCAL model is $O(d^2 + \log^* n)$. In stark contrast, under the criterion $p2^d \leq 1$, there is a randomized lower bound of $Ω(\log \log n)$ by Brandt et al. [STOC'16] and a deterministic lower bound of $Ω(\log n)$ by Chang, Kopelowitz and Pettie [FOCS'16]. Brandt, Maus and Uitto conjectured that the same behavior holds for the unrestricted setting where each random variable affects arbitrarily many events. We prove their conjecture, by providing an algorithm that solves the LLL in time $O(d^2 + \log^* n)$ under the LLL criterion $p2^d < 1$, which is tight in bounded-degree graphs due to an $Ω(\log^* n)$ lower bound by Chung, Pettie and Su [PODC'14]. By the work of Brandt, Maus and Uitto, obtaining such an algorithm can be reduced to proving that all members in a certain family of functions in arbitrarily high dimensions are convex on some specific domain. Unfortunately, an analytical description of these functions is known only for dimension at most $3$, which led to the aforementioned restriction of their result. While obtaining those descriptions for functions of (substantially) higher dimension seems out of the reach of current techniques, we show that their convexity can be inferred by combinatorial means.
