论文标题
改进了Lovász本地引理和边缘着色的分布式算法
Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
论文作者
论文摘要
Lovász局部引理是概率理论的经典结果，通常用于通过概率方法证明组合对象的存在。它以最简单的形式指出，如果我们有$ n $“不良事件”，每种事件最多都有$ p $，并且除了$ d $ $ d $其他事件以外的所有事件，那么在$ p $和$ d $的某些标准下，所有不良事件都可以以积极的可能性来避免。 尽管原始证据是存在的，但已经对算法Lovász局部引理进行了很多研究：也就是说，设计了一种算法，该算法找到了基本的随机变量的分配，以便避免所有不良事件。值得注意的是，Moser和Tardos [JACM '10]的著名结果也暗示了该问题有效的分布式算法，以$ O（\ log^2 n）$ rounds运行。对于低$ d $的实例，这将提高到$ o（d^2+\ log^{o（1）} \ log n）$由Fischer和Ghaffari [Disc '17]，这一结果在分布式复杂性理论（Chang and Pettie [Sicomp '19]）中非常重要。 我们为Lovász本地引理提供了改进的算法，在有关$ p $和$ d $的标准的实力与分布式圆形复杂性之间提供了权衡。特别是，在与Fischer和Ghaffari的算法相同的机制下，我们将圆的复杂性提高到$ O（\ frac {d} {\ log d}+d}+\ log^log^{o（1）} \ log n）$。在权衡取舍的另一端，我们获得了比以前所知的$ \ log^{o（1）} \ log n $圆形复杂性。 作为我们的主要应用程序，我们还提供了第一个$ \ log^{o（1）} \ log n $ round分布式算法，以解决$δ+o（δ）$ - edge tragral of tem $Δ$的问题。这几乎是对先前结果的几乎指数改进：没有先前的$ \ log^{o（1）} n $ round算法甚至以$2δ-2$ - 边缘着色而闻名。
The Lovász Local Lemma is a classic result in probability theory that is often used to prove the existence of combinatorial objects via the probabilistic method. In its simplest form, it states that if we have $n$ `bad events', each of which occurs with probability at most $p$ and is independent of all but $d$ other events, then under certain criteria on $p$ and $d$, all of the bad events can be avoided with positive probability. While the original proof was existential, there has been much study on the algorithmic Lovász Local Lemma: that is, designing an algorithm which finds an assignment of the underlying random variables such that all the bad events are indeed avoided. Notably, the celebrated result of Moser and Tardos [JACM '10] also implied an efficient distributed algorithm for the problem, running in $O(\log^2 n)$ rounds. For instances with low $d$, this was improved to $O(d^2+\log^{O(1)}\log n)$ by Fischer and Ghaffari [DISC '17], a result that has proven highly important in distributed complexity theory (Chang and Pettie [SICOMP '19]). We give an improved algorithm for the Lovász Local Lemma, providing a trade-off between the strength of the criterion relating $p$ and $d$, and the distributed round complexity. In particular, in the same regime as Fischer and Ghaffari's algorithm, we improve the round complexity to $O(\frac{d}{\log d}+\log^{O(1)}\log n)$. At the other end of the trade-off, we obtain a $\log^{O(1)}\log n$ round complexity for a substantially wider regime than previously known. As our main application, we also give the first $\log^{O(1)}\log n$-round distributed algorithm for the problem of $Δ+o(Δ)$-edge coloring a graph of maximum degree $Δ$. This is an almost exponential improvement over previous results: no prior $\log^{o(1)} n$-round algorithm was known even for $2Δ-2$-edge coloring.
