论文标题
在动态网络中的信息传播的平滑分析
Smoothed Analysis of Information Spreading in Dynamic Networks
论文作者
论文摘要
$ k $ - 米斯奇（Message）的最著名解决方案在Dynamic size $ n $的动态网络中广播需要$ω（nk）$ rounds。在本文中，我们看看是否可以通过平滑的分析来改善这些界限。我们可能会在这种情况下研究最自然的随机算法，用于传播令牌：在每个时间步骤中，选择一个令牌以从您知道的一组令牌中随机广播。我们表明，即使是少量的平滑（每回合添加一个随机边缘），这种自然策略也可以解决$ k $ -sessage以$ \ tilde {o}（n+k^3）$ rounds的广播，具有很高的可能性，超过了$ k = o（\ sqrt {n} $ for $ k）$（n+k）$（n+k）（n+k）（n+k）（n+k）（n+k）（ $ k = o（n^{1/3}）$（忽略对数因素）。实际上，我们显示的主要结果甚至更强大，更一般：给定$ \ ell $ -smooth（即$ \ ell $每回合添加的$ \ ell $随机边缘），这种简单的策略终止于$ O（kn^{2/3} \ log^\ log^{1/3} {1/3}（1/3}（n）（n）（n）（n）\ ell^ell^ell^{ - 1/3} { - 1/3}）$ rounds。然后，我们通过几乎匹配的下限证明了这种分析几乎紧密的。为了更好地理解平滑对信息传播的影响，我们接下来将注意力转向静态网络，证明了$ \ tilde {o}（k \ sqrt {n}）$ rounds的紧密界限以解决$ k $ -message广播，这比我们在动态设置中可以实现的策略更好。这证实，尽管平滑的分析减少了变化的图形结构引起的困难，但并不能完全消除它们。最后，我们使用工具来证明在没有平滑度的情况下，在所谓的良好网络中广播$ k $ - 米斯奇的最佳结果。通过将该结果与混杂良好的网络的现有下限进行比较，我们在忽略和强烈适应性的对手之间建立了正式的分离，就混合的令牌传播而言，部分解决了关于对手强度对$ k $ $ $ - $ - 梅斯及时广播问题的公开问题。
The best known solutions for $k$-message broadcast in dynamic networks of size $n$ require $Ω(nk)$ rounds. In this paper, we see if these bounds can be improved by smoothed analysis. We study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (one random edge added per round), this natural strategy solves $k$-message broadcast in $\tilde{O}(n+k^3)$ rounds, with high probability, beating the best known bounds for $k=o(\sqrt{n})$ and matching the $Ω(n+k)$ lower bound for static networks for $k=O(n^{1/3})$ (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given $\ell$-smoothing (i.e., $\ell$ random edges added per round), this simple strategy terminates in $O(kn^{2/3}\log^{1/3}(n)\ell^{-1/3})$ rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of $\tilde{O}(k\sqrt{n})$ rounds to solve $k$-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply our tools to prove an optimal result for $k$-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the $k$-message broadcast problem.
