论文标题
改进了通过降低的分布式网络分解，击打集和跨度
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
论文作者
论文摘要
本文介绍了分布式图算法领域的某些关键问题（包括网络分解，击球集和跨度）的确定性算法。作为这些结果的主要成分，我们开发了新型的随机分布算法，我们只能使用成对独立性来分析这些算法，因此我们可以有效地取代。作为我们最突出的最终重点，我们获得了$ o（\ log n）$ - 颜色$ o（\ log n \ cdot \ log \ log \ log \ log \ log n）$ - $ \ tilde {o}中的强直径网络分解的确定性结构。这是在两个参数中实现几乎$ \ log n $的第一个结构，它在确定性分布式网络分解方面的令人兴奋的进度[Rozhoň，Ghaffari Stoc'20; Ghaffari，Grunau，RozhoňSoda'21; Chang，Ghaffari Podc'21; Elkin，Haeupler，Rozhoň，Grunau Focs'22]。
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the main ingredient in these results, we develop novel randomized distributed algorithms that we can analyze using only pairwise independence, and we can thus derandomize efficiently. As our most prominent end-result, we obtain a deterministic construction for $O(\log n)$-color $O(\log n \cdot \log\log\log n)$-strong diameter network decomposition in $\tilde{O}(\log^3 n)$ rounds. This is the first construction that achieves almost $\log n$ in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions [Rozhoň, Ghaffari STOC'20; Ghaffari, Grunau, Rozhoň SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozhoň, Grunau FOCS'22].
