A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
复制标题
Lovász 局部引理的分布式复杂性的尖锐阈值现象
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jara Uitto
中科院分区：
文献类型：
--
作者：
S. Brandt;Yannic Maus;Jara Uitto
Lovász局部引理（LLL）表示，给定一组取决于某些随机变量值的不良事件，并且每个事件发生的概率最多为p，并且最多取决于d个其他事件，如果满足LLL标准ep（d+1）<1，则存在避免所有不良事件的变量分配。如今，在分布式图算法领域，它也已成为一个强大的框架开发-主要是随机-算法。Moser和Tardos的一个经典结果给出了分布式Lovász局部引理的O（log^2 n）算法[JACM'10]，如果ep（d + 1）< 1满足。如果有更强的标准，即，要求更小的错误概率，可以想象我们可以找到更好的算法。实际上，例如Chung，Pettie和Su [PODC'14]在epd^2 < 1标准下给出了O（log_epd^2 n）算法。更进一步，Ghaffari，Harris和Kuhn引入了一个2^O（log log n）时间算法，给定d^8 p = O（1）[FOCS'18]。在消极的一面，勃兰特等人。Chang et al.证明了在标准pleq 2^-d下，我们不能分别低于Ω（log log n）（随机）[STOC'16]和Ω（log n）（确定性）[FOCS'16]。此外，Ω（log^* n）存在一个对任何标准都成立的下界。在本文中，我们研究的依赖关系的分布式复杂性的LLL问题上选择的LLL标准。我们表明，对于所考虑的LLL实例的每个随机变量与输入图的边缘相关联的基本情况，即每个随机变量最多影响两个事件，在p = 2^-d处发生尖锐的阈值现象：我们提供了一个简单的确定性（！）如果p < 2^-d，则匹配有界度图中的Ω（log^* n）下界的算法，而对于p \geq 2^-d，Ωmega（log log n）随机化和Ω（log n）确定性下界成立。在许多应用中，变量影响两个以上的事件，我们的主要贡献是扩展我们的算法的情况下，随机变量的影响最多三个不同的坏事件。令人惊讶的是，我们发现，尖锐的阈值发生在完全相同的点上，这为我们的猜想提供了证据，即这种现象总是发生在p = 2^-d处，与受变量影响的事件数r无关。几乎所有的步骤，我们提供的情况下r=3的证明框架直接延伸到任意r的情况下，因此，我们的方法作为一个步骤来表征的复杂性的LLL在不同的指数标准。
The Lovász Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most p and depends on at most d other events, there is an assignment of the variables that avoids all bad events if the LLL criterion ep(d+1)<1 is satisfied. Nowadays, in the area of distributed graph algorithms it has also become a powerful framework for developing---mostly randomized---algorithms. A classic result by Moser and Tardos yields an O(log^2 n) algorithm for the distributed Lovász Local Lemma [JACM'10] if ep(d + 1) < 1 is satisfied. Given a stronger criterion, i.e., demanding a smaller error probability, it is conceivable that we can find better algorithms. Indeed, for example Chung, Pettie and Su [PODC'14] gave an O(log_epd^2 n) algorithm under the epd^2 < 1 criterion. Going further, Ghaffari, Harris and Kuhn introduced an 2^O(√log log n ) time algorithm given d^8 p = O(1) [FOCS'18]. On the negative side, Brandt et al.\ and Chang et al.\ showed that we cannot go below Ω(log log n) (randomized) [STOC'16] and Ω(log n) (deterministic) [FOCS'16], respectively, under the criterion pleq 2^-d . Furthermore, there is a lower bound of Ω(log^* n) that holds for any criterion. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at p = 2^-d : we provide a simple deterministic (!) algorithm that matches the Ω(log^* n) lower bound in bounded degree graphs, if p < 2^-d , whereas for p \geq 2^-d , the Ωmega(log log n) randomized and the Ω(log n) deterministic lower bounds hold. In many applications variables affect more than two events; our main contribution is to extend our algorithm to the case where random variables influence at most three different bad events. We show that, surprisingly, the sharp threshold occurs at the exact same spot, providing evidence for our conjecture that this phenomenon always occurs at p = 2^-d , independent of the number r of events that are affected by a variable. Almost all steps of the proof framework we provide for the case r=3 extend directly to the case of arbitrary r; consequently, our approach serves as a step towards characterizing the complexity of the LLL under different exponential criteria.
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
局部模型的时间层次定理
影响因子：
1.6
作者：
Chang, Yi-Jun;Pettie, Seth
通讯作者：
Pettie, Seth