Smoothed Analysis for Distributed MIS

Smoothed Analysis for Distributed MIS Dipan Dey∗

Fabien Dufoulon†

William K. Moses Jr.‡

Gopal Pandurangan∗

Abstract

arXiv:2611.16302v1 [cs.DC] 12 Nov 2026

We study smoothed analysis for the distributed Maximal Independent Set (MIS) problem, a fundamental problem in distributed computing. For many decades, the best-known round complexity of distributed MIS was O(log n), achieved by the seminal Luby’s algorithm [STOC 1985, SICOMP 1986], and a long-standing open problem was whether p a significantly faster algorithm exists. The best lower bound known for a while was Ω( log√n/ log log n) [Kuhn, Moscibroda, Wattenhofer, JACM 2016], which was recently improved to Ω( log n) [Khoury and Schild, FOCS 2025]. Very recently, Khoury and Schild [Arxiv, 2026] made a major breakthrough, showing that Ω(log n/ log log n) is a lower bound for any MIS algorithm (even) in the LOCAL model; this means that Luby’s algorithm is essentially optimal (up to a log log n factor). The lower bound shown is existential, i.e., there exist graphs where this lower bound holds for any MIS algorithm. The above lower bound result for MIS raises an important question: how robust (or fragile) is the MIS problem in relation to obtaining significantly faster algorithms? Motivated by this question, we study smoothed analysis of distributed MIS. In smoothed analysis, given an arbitrary (input or base) graph G, we smooth (perturb) it by adding/deleting a small amount of random edges. In particular, if G is a graph of n nodes, we consider the smoothed graph Gs = G△G(n, p), where G(n, p) is an Erdős-Rényi random graph (△ denotes the symmetric difference). The goal is to show whether one can obtain significantly faster algorithms for as small a p as possible, and if so, to quantify the required p (which captures the amount of randomness needed to smooth). Our main results are almost tight bounds on the round complexity of smoothed MIS vis-à-vis the smoothing parameter p: 1. For every base graph G, smoothing with parameter p = β ln n/n (for some sufficiently large constant β), there is a randomized LOCAL algorithm that, given only the smoothed graph √ Gs = G△G(n, p), computes an MIS of Gs in O( log n) rounds with high probability.1 This is (almost) quadratically faster than the worst-case bound of Ω(log n/ log log n) [Khoury and Schild, 2026] as well as the best-known MIS algorithm of Luby [STOC 1985]. 2. We show that the above smoothing parameter is optimal up to a constant factor for achieving such a significantly faster runtime. More precisely, if p ≤ (1/2 − δ) ln n/n for a constant δ > 0, then there is some base graph G on which every randomized LOCAL MIS algorithm needs Ω(log n/ log log n) rounds on the smoothed graph Gs ; in other words, there is no advantage in smoothing. Our results are the first of their kind for distributed graph algorithms for local problems, and they show that smoothed analysis provides a way to overcome lower-bound barriers for well-studied problems in distributed graph algorithms. ∗

Department of Computer Science, University of Houston, Houston, TX 77204, USA. Email: ddey@central.uh.edu and gopal@cs.uh.edu. Research supported in part by ARO Grant W911NF-231-0191, NSF grant CCF-2402837, and NSF grant CCF-2552882. † Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France. Email: fabien.dufoulon@labri.fr. ‡ Department of Computer Science, Durham University, Durham, UK. Email: william.k.moses-jr@durham.ac.uk. 1 Throughout, this means with probability at least 1 − n−c , where c > 0 is an arbitrary constant fixed in advance.

Contents 1 Introduction 1.1 Smoothed Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Smoothed Analysis of Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The Maximal Independent Set (MIS) Problem . . . . . . . . . . . . . . . . . . . . . 1.4 Smoothed Analysis of Distributed MIS . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 High-level Overview of our Results & Technical Challenges . . . . . . . . . . . . . . 1.8 Additional Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 1 2 3 4 5 6 8

2 Preliminaries

9

3 Structural Properties of Smoothed Graphs 3.1 Smoothed Diameter of Large Two-Hop Neighborhoods . . . . . . . . . . . . . . . . . 3.2 Most Randomly Sampled Vertices Are Isolated . . . . . . . . . . . . . . . . . . . . . √ 4 An O( log n)-round Smoothed MIS Algorithm 4.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Algorithm Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Proof of Lemma 4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Extension to the Symmetric Difference Model . . . . . . . . . . . . . . . . . . . . . .

11 11 14 17 17 18 20 29 29

5 Lower Bound: Less Smoothing Gives No Advantage 5.1 Proof Sketch of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Reduction from MIS to MIS on Smoothed Graphs . . . . . . . . . . . . . . . . . . . 5.3 Obtaining the Ω(ln n/ ln ln n) Lower Bound . . . . . . . . . . . . . . . . . . . . . . . 5.4 Allowing Both Edge Additions and Deletions during Smoothing . . . . . . . . . . . .

30 30 32 38 39

AI Disclosure

39

A Proof of Lemma 2.2

42

1

Introduction

1.1

Smoothed Analysis

In this work, we study smoothed analysis of a fundamental problem in distributed computing, namely the Maximal Independent Set (MIS) problem. Spielman and Teng’s seminal work [32] introduced smoothed analysis of algorithms to explain why the popular simplex algorithm for linear programming does very well in practice, despite having a worst-case exponential run time. At a high level, smoothed analysis involves perturbing a given input instance (which can be a “bad” instance) with random noise and then analyzing the algorithm’s (expected) performance on the perturbed input (where the expectation is taken with respect to the random noise and possibly the random choices of the algorithm, if it is randomized). In particular, smoothed analysis of the simplex algorithm involves perturbing the input data with a small amount of Gaussian noise (with mean zero, parameterized by the variance of the noise) and then showing that the perturbed input can be solved efficiently in (expected) polynomial time by the simplex algorithm. In fact, Spielman and Teng show that the run time depends on the perturbation; the more the perturbation, i.e., the larger the variance of the added noise, the faster the run time. Smoothed analysis has since become an important paradigm for going beyond worst-case analysis of algorithms. Smoothed analysis differs from worst-case analysis, which is determined by the algorithm’s performance on the worst input. It may be that only a few inputs yield poor performance, while on the vast majority of inputs performance is significantly better. Thus, while the worst-case lower bounds the performance of the algorithm on any input, such worst-case inputs can be few and often specially constructed (e.g., the input that forces simplex algorithm to take exponential time). Hence, such lower bounds can be called fragile. Smoothed analysis also differs from average-case analysis, another well-studied paradigm for addressing the “fragility” of worst-case analysis. In average-case analysis, we assume a probability distribution on the set of all possible inputs and analyze the expected performance of the algorithm.2 While average-case analysis may not be determined only by performance on a small number of inputs, its weakness is that the chosen input distribution may not reflect real-world inputs, and its performance may depend mainly on the chosen distribution (which is typically taken to be uniform over all inputs). Smoothed analysis can be thought of as a hybrid, combining the good aspects of both worstcase and average-case analysis — it considers any input (including worst-case inputs) and then randomly perturbs it. If even small perturbations (by adding random noise) lead to significantly better performance, then the worst case is quite sensitive to the input parameters. In practice, there is usually noise, so the algorithm is likely to avoid worst-case behavior.

1.2

Smoothed Analysis of Graph Isomorphism

To illustrate a recent “success story” for smoothed analysis in the centralized setting, we consider a well-known graph-theoretic problem: graph isomorphism. The best-known algorithm for graph isomorphism takes quasi-polynomial time [5, 4], and it is not known whether the problem admits a polynomial-time algorithm. On the other hand, an average-case analysis has been very well studied. This is known as random graph isomorphism where one compares a G(n, p) (Erdős-Rényi) random graph with an arbitrary graph. In particular, an early result by Babai, Erdős, and Selkow [6] showed 2

Again, the expectation is with respect to the input distribution as well as possibly the random choices made by the algorithm, in case it is randomized.

1

that random graph isomorphism can be solved efficiently (in linear expected time) for G(n, 1/2), which models a graph drawn randomly from the space of all graphs on n nodes. Later, these results were extended to a much sparser regime of p [9, 12, 26]. These results crucially exploit properties of random graphs. However, they do not address the original problem where both graphs can be arbitrary. In graphs, smoothed analysis typically involves adding (or deleting) a small amount of random edges to a given arbitrary input graph G — we call this the base graph (cf. Section 1.5). The recent works of [3, 15] study smoothed analysis of graph isomorphism, where we compare two arbitrary graphs, but one of them is smoothed by adding a small amount of random edges — by adding a G(n, p) (Erdős-Rényi) random graph with p = O(log n/n). More precisely, given G, they consider the symmetric difference graph — G△G(n, p) — where each existing edge is also deleted with probability p (our smoothed model is also the same). They show that graph isomorphism between a smoothed graph and an arbitrary graph can be solved in polynomial time. In fact, they show a similar polynomial time solvability (via a more complicated algorithm) for even smaller p = O(1/n). However, if p = o(1/n), they show that smoothing is not very helpful as it essentially reduces to solving isomorphism on a hard instance of the base graph G (see [3] for more details).

1.3

The Maximal Independent Set (MIS) Problem

The maximal independent set (MIS ) problem is one of the most fundamental and well-studied problems in distributed graph algorithms. Given a graph with n nodes, each node must decide whether it belongs to a subset M ⊆ V (called the MIS) or not such that (i) every node is either in M or has a neighbor in M and (ii) no two nodes in M are adjacent to each other. Because of the importance of MIS, distributed algorithms for MIS have been studied extensively for the last four decades mainly with a focus on improving the time complexity (i.e., the number of rounds). In 1986, Alon, Babai, and Itai [2] and Luby [27] presented a randomized distributed MIS algorithm that runs in O(log n) rounds (where n is the number of nodes in the graph) with high probability. Since these seminal results, significant progress has been made in designing progressively faster distributed MIS algorithms [8, 16, 30]. The currently best-known algorithm in the LOCAL model takes O(log ∆ + poly(log log n)) rounds [30, 19].3 Thus, the currently known best algorithms of MIS ([30, 18, 16]) are dependent on ∆ (the maximum degree), and hence still take O(log n) rounds (even in the LOCAL model) for graphs with O(nΩ(1) ) degree. As far as deterministic algorithms are concerned, the best known algorithms take O(poly(log n)) rounds in the LOCAL and CONGEST models [30, 18]. There are faster distributed algorithms known for special classes as trees [16, 25] √ of graphs such 4 and Erdős-Rényi random graphs [16, 23], but they still take O( log n) rounds. There is also a fast deterministic distributed algorithm running in O(log∗ n) for growth-bounded graphs (which includes unit-disk graphs) [31]. There are also MIS algorithms that run faster on graphs with low arboricity, but they nevertheless take O(log n) rounds on high arboricity graphs [16, 7]. While the above results make significant progress on the round complexity of the MIS problem for some specific graphs, in general graphs the best known running time is still O(log n) (even for randomized model). Till recently, the best-known lower bound for MIS qin the LOCAL o  nalgorithms was Ω min

log ∆ log log ∆ ,

log n log log n

rounds due to Kuhn, Moscibroda, and Wattenhofer [24] that also

3 The currently best-known randomized algorithm in the CONGEST model takes O(log ∆ log log n+poly(log log n)) rounds [18]. See Section 1.5 for definitions of LOCAL and CONGEST models — two standard models in distributed computing. √ 4 The algorithm in [23] for G(n, p) random graphs actually takes O( log n log log n) rounds, though it is claimed p it takes O( log n/ log log n) (due to a calculation error).

2

applies to randomized algorithms and holds even in the LOCAL model. This lower bound was later √ improved to Ω( log n) by Khoury and Schild in 2025 (in the LOCAL model) [21]. Thus till very recently (see next), there existed essentially a quadratic gap between the known upper and lower bounds for the round complexity of MIS. Very recently, in October 2026, Khoury and Schild [22], in a major breakthrough, announced that Ω(log n/ log log n) is a lower bound for any MIS algorithm (even) in the LOCAL model; this means that Luby’s algorithm is essentially optimal (up to a log log n factor). This lower bound is existential; it applies to specially constructed graphs. Even prior to this result, the status of the MIS problem gave a good motivation for studying smoothed analysis, as no algorithm with o(log n) rounds was known; but the new result motivates studying smoothed complexity of MIS even more, as it rules out getting any algorithm substantially better (up to a log log n factor) than Θ(log n) in the worst case.

1.4

Smoothed Analysis of Distributed MIS

In this paper, we initiate a study of smoothed analysis for distributed graph algorithms for local problems by focusing on the fundamental MIS problem. Local problems (not to be confused with the LOCAL model — cf. Section 1.5) are problems that admit algorithms that are significantly faster than the diameter of the graph, typically running in polylog n rounds.5 They include fundamental problems such as MIS, maximal matching, and coloring. Our motivation is simple: Can we use smoothed analysis to overcome the (essentially) Θ(log n) lower bound barrier of distributed MIS? As mentioned earlier, a natural smoothing model for studying graph problems in prior work (see e.g., [3, 15, 13, 14]) is adding (and deleting) a small number of random edges to the given graph G (called the base graph). More precisely, this is typically done by adding a G(n, p) random graph to the base graph. In other words, for each pair of nodes, an edge is added with probability p independently of the others (if an edge already existed between the node pair, then this does nothing). One may also delete an existing edge with probability p. We will mainly focus on adding random edges, i.e., the smoothed graph G = G ∪ G(n, p), since both our upper and lower bounds also apply when edges are deleted (see the end of this subsection, Sections 4.3 and 5.4). Why should smoothing give substantially better bounds than without? One main intuition is that (this is conceptually analogous to the situation in the graph isomorphism problem) the average case analysis of distributed MIS, i.e., on random graphs, gives a substantially better bound. As √mentioned earlier, distributed MIS on G(n, p) random graphs (for every p) can be solved in O( log n) rounds [16, 23] — this is the best known bound if p is arbitrary. As discussed in Section 1.3, this is almost quadratically faster than the recent lower bound of Ω(log n/ log log n) as well as the best-known general upper bound of O(log n) (e.g., Luby’s algorithm [27]) that has stood for over four decades. So a key question is: can we obtain a substantially faster algorithm — in √ particular an O( log n)-round MIS algorithm — via smoothed analysis for any arbitrary (base) graph G? And if so, what is the smallest p (the smoothing parameter) needed? We want to keep the number of added random edges as small as possible. √ Our main result answers the above question in the affirmative: one can obtain a O( log n)round MIS algorithm (cf. Section 1.6 for a precise statement and Section 4 for the algorithm) for p = O(log n/n), i.e., by adding O(n log n) random edges to G. We also show that this amount 5

On the other hand, global problems need at least the graph diameter number of rounds, since they involve traversing the whole network. They include fundamental problems such as broadcast, leader election, and minimum spanning tree (MST) construction. Smoothed analysis in the context of distributed algorithms has been applied earlier for the MST problem [10] as well as for dynamic networks — cf. Section 1.8 for details.

3

√ of smoothing is the best possible for obtaining an O( log n)-round algorithm, in the sense that Ω(n log n) random edges need to be added for some base graph G (this also illustrates why smoothed analysis is a hybrid of both worst-case and average-case analysis: it is worst case in the base graph G and average-case in the amount of random edges added). Our results seem quite robust with respect to both the runtime obtained and √ the amount of smoothing. We note that, in general, it is unclear how to obtain better than log n rounds via smoothing, i.e., even if we use a larger p. As mentioned √ earlier, if the base graph itself is taken to be a G(n, p) random graph, in particular, say if p = 2 log n /n, then smoothing adds/deletes only a small number of random edges and thus boils down to finding √ an efficient distributed algorithm for such a G(n, p) graph. Currently, neither a faster than O( log n) round algorithm nor a matching lower bound is known for G(n, p) random graphs, and it seems hard to significantly improve this bound by more than a poly(log log n) factor.6 We also point out that our results (both upper and lower bounds) also apply if we smooth by also deleting edges, i.e., say we delete each existing edge (independently) with probability p, i.e.,√the smoothed graph is the symmetric difference between the base graph G and G(n, p). The O( log n) upper bound holds for p = O(log n/n); informally, this follows by writing G△G(n, p) as 7 the smoothing √ of a random subgraph of G (Section 4.3). Again, as mentioned earlier, improving on the √ O( log n) runtime seems hard, since the base itself can be taken to be a G(n, p) with p = 2 log n /n and deleting a few random edges does not make a difference. Also, our lower bound holds in both models: if p ≤ (1/2 − δ) ln n/n for a constant δ > 0, that is, if fewer than 14 n ln n edges are added or deleted in expectation, then there is no advantage in smoothing — there is a base graph that requires Ω(log n/ log log n) rounds (cf. Section 5). Conceptually, our MIS results mirror those obtained for the graph isomorphism, albeit under very different settings. For MIS, “hard” means breaking the Θ(log n) barrier for arbitrary graphs (as opposed to the quasi-polynomial barrier for graph isomorphism for arbitrary graphs) using smoothing and showing that the amount of smoothing needed√is essentially tight, i.e., Θ(n log n) random edges added/deleted are required for obtaining an O( log n)-round algorithm (for graph isomorphism it is adding/deleting Θ(n) edges for polynomial time algorithms). Thus, smoothed analysis seems to be a promising “beyond worst-case analysis” technique even for distributed graph problems such as MIS.

1.5

Model

Smoothing Model. We are given an arbitrary graph G, called the base graph. We smooth G as follows. Given a smoothing parameter p ∈ [0, 1], for each pair of nodes of G, flip it with probability p, i.e., each non-edge becomes an edge with probability p and each edge becomes a non-edge with probability p. Let the resulting graph be Gs . In other words, Gs = G△G(n, p), where G(n, p) is the (standard) Erdős-Rényi random graph and △ denotes the symmetric difference between the two graphs (the graph with the same set of nodes and the set of edges that are either only present in G or only present in G(n, p) but not both). As mentioned in Section 1.2, this model is quite natural for smoothing in graphs (this is the same model used in [3, 15]), and this model and similar ones have been used in several prior works, including in distributed algorithms [13, 10, 14]. In our analysis, we also use G, which denotes the smoothed graph under just additions, i.e., G = G ∪ G(n, p). It turns out that it is simpler to analyze G rather than Gs ; it is easy to extend the results obtained 6

p In fact, ChatGPT claims an O( log n/ log log n) bound for G(n, p) random graphs, but nothing better. Also see footnote 4. 7 One can argue that the probability that a deleted edge is added is negligible; for a more precise analysis see Section 4.3.

4

for G to Gs (cf. Section 4.3).8 Distributed Computing Model. We have a distributed network of n nodes, modeled as an undirected graph. Each node hosts a processor with limited initial knowledge. We assume that each node has a distinct ID of size O(log n) bits. We assume that each node has ports (each port having a unique port number); each incident edge is connected to one distinct port. We assume that each node knows n. The smoothed graph Gs (or G) serves as input to the algorithm. We do not assume that the algorithm knows which edges were added or deleted. For our upper bound (i.e., distributed algorithm — cf. Section 4), we assume that nodes do not know the smoothing parameter p nor can they distinguish which incident edges are random and which belonged to the base graph G (or got deleted). On the other hand, our lower bound (cf. Section 5) holds even if nodes know p and even if they know which edges are random and which belong(ed) to G (including knowing which edges were deleted). Nodes are allowed to communicate through the edges of the smoothed graph, and it is assumed that communication is synchronous and occurs in rounds. We identify each node of the network with a vertex of the smoothed graph, and use the two terms interchangeably. In particular, we assume that each node knows the current round number (starting from round 0). In each round, each node can perform some local computation (which finishes in the same round), including accessing a private source of randomness. We assume the LOCAL model, a standard model [29] with no restriction on the size of messages sent per edge per round.9

1.6

Our Contributions

Our main conceptual contribution is positing a smoothed analysis of distributed MIS, motivated by the desire to go beyond its worst-case runtime bound of Ω(log n/ log log n) [22] in arbitrary graphs. Even before this lower bound was established, the best-known runtime was O(log n), which the classical Luby’s algorithm [27] achieves. Our main technical results are almost tight bounds on the round complexity of smoothed MIS vis-à-vis the smoothing parameter p: 1. (cf. Theorem 4.14) For every base graph G and smoothing with parameter p = β ln n/n (for some sufficiently large constant β), there is a randomized LOCAL algorithm √ that, given only the smoothed graph Gs = G△G(n, p), computes an MIS of Gs in O( log n) rounds with high probability.10 This is almost quadratically faster than the worst-case bound of Ω(log n/ log log n)[22] and the best-known (in terms of the parameter n) runtime of O(log n) [27]. 2. (cf. Theorem 5.8) We show that the above smoothing parameter is optimal up to a constant factor for achieving such a significantly faster runtime. More precisely, if p ≤ (1/2 − δ) ln n/n for a constant δ ∈ (0, 1/2], then there is a base graph G such that every randomized LOCAL algorithm that computes an MIS of the smoothed graph Gs with constant success probability takes Ω(log n/ log log n) rounds; in other words, this amount of smoothing gives no advantage. 8 We use Gs to denote the smoothed graph under the symmetric difference, to distinguish it from G = G ∪ G(n, p), which is smoothed by additions only. 9 The other standard model is the CONGEST model, where only O(log n) bits can be exchanged per edge per round. 10 Throughout, this means with probability at least 1 − n−c , where c > 0 is an arbitrary constant fixed in advance.

5

Our results are the first of their kind for distributed graph algorithms for local problems such as MIS, and they show that smoothed analysis provides a way to overcome lower-bound barriers for well-studied problems in distributed graph algorithms.

1.7

High-level Overview of our Results & Technical Challenges

Smoothed Algorithm and its Analysis. Our algorithmic result (Theorem 4.14) shows √ that smoothing with p = β ln n/n, for a sufficiently large constant β, makes MIS solvable in O( log n) LOCAL rounds with high probability, for every base graph G. The algorithm sees only the smoothed graph Gs : it cannot tell base edges from random ones. The random edges are both part of the communication network and part of the input, since the output must be an MIS of Gs . Our analysis focuses on adding random edges only, i.e., the smoothed graph G = G ∪ G(n, p); as argued in Section 4.3, it can be extended to Gs , i.e., under both additions and deletions. The basic high-level intuition comes from the analysis of distributed MIS in G(n, p) random √ √ graphs [23, 16]. If p = O(2 log n /n), then the degree of a node is O(2 log n ) with high probability √ and hence one can simply use the degree-sensitive algorithm of Proposition 2.3 to obtain a O( log n)√ round√algorithm. On the other hand, if p = Ω(2 log n /n), then the diameter of the G(n, p) graph is O( log n) (this follows from the fact that the diameter D of a G(n, p) graph is O(log n/ log(np)) with high probability — cf. Lemma 2.2); hence one can simply collect all the topology information in a single node in the LOCAL model in O(D) rounds and compute the MIS locally in the node and distribute the answers to all nodes in another O(D) rounds. In smoothed analysis, when the base graph G is arbitrary, there are key technical challenges in implementing the above intuition. Call a node low-degree if its degree in G is at most a threshold √ ln n B=e , and high-degree otherwise. Of course, if all nodes in G have low degree (note that the difference in degree of a node in G versus G is O(log n), which is quite small if the node’s degree is high), then one can immediately obtain the result by applying the degree-sensitive algorithm. However,√some (or even all) nodes can have high degree; unlike the G(n, p) case, this does not imply O( log n) diameter of the smoothed graph, since the added edges form a G(n, p) graph with p = O(log n/n), which is very small. Next, consider the other extreme case where all nodes have high degree. In this case, one can show that the vertices can be partitioned into n′ = O(n/B) parts of size Θ(B), such that any two vertices of a part are within constant distance in G (Lemma 3.2). Two parts span Θ(B 2 ) vertex pairs, so a random edge joins them with probability p′ = Ω(pB 2 ), which is much larger than p. Viewing each part√as a single node, the parts therefore behave like a G(n′ , p′ ) random graph, whose √ diameter is O( log n) (cf. Lemma 2.2). Hence, the diameter of the smoothed graph is also O( log n) (Lemma 3.1), and we can again gather the topology, using the primitive of Lemma 2.4. The bulk of the technical complication arises when G (and hence G) contains both high-degree and low-degree nodes. First consider the subgraph induced by the√low-degree nodes. The degreesensitive algorithm of Proposition 2.3 handles these nodes in O( log n) rounds. The difficulty lies in the high-degree vertices, which our algorithm removes first, in two steps (Section 4.1). In the first step, every high-degree vertex marks each edge to a low-degree neighbor with probability about 1/2. Every low-degree vertex with a marked edge and no (low-degree) neighbor that also has a marked edge joins the MIS. This low-degree MIS node serves as a helper, dominating the high-degree vertices next to it. In the second√step, the remaining high-degree vertices learn their components by gathering information for O( log n) rounds, using all nodes as relays, and solve MIS locally on the components. A completeness check ensures that this step never outputs two adjacent vertices; only maximality depends on the random edges. The main challenge is to show that, with high probability, either no high-degree vertex remains 6

√ after the first step, or all remaining ones are pairwise within distance O( log n) in G (Section 4.2). Although the algorithm never sees G, the analysis distinguishes cases using sets defined solely from G. In Lemma 3.1, we show that if many vertices are within two hops √ of vertices of large degree in G, then the random edges shrink the diameter of this region to O( log n). Otherwise, the helpers dominate every high-degree vertex. The technical difficulty is dealing with the low-degree helper nodes in the first step. The potential helpers of a high-degree vertex are the low-degree neighbors it reaches by a marked edge; such a vertex becomes a helper only if none of its neighbors has a marked edge. Two potential helpers of the same high-degree vertex therefore have dependent outcomes if they are adjacent or have a common neighbor (in this case, if the common neighbor is also a potential helper, then neither of them becomes a helper vertex). Moreover, other high-degree vertices may prevent a potential helper from joining by marking edges to its neighbors. A counting argument in Lemma 3.5 shows that all but a constant number of the potential helpers are pairwise at distance at least three, which makes their outcomes independent. We then show that each such potential helper is, with constant probability, not blocked by marked edges by any vertex of large degree in G. The crucial intuition behind this analysis is to exploit the additional random edges introduced by smoothing. Note that a high-degree node v in the base graph G might have low-degree nodes with an arbitrary connectivity structure among them; e.g., they can form a clique. In this case, with high probability no low-degree neighbor of v in G will join the MIS, since it is likely that at least one of its neighbors (which is also a neighbor of v) is also marked by v. However, if there are lots of low-degree nonneighbors of v in G, then it is likely that one of them (say u) will become a low-degree neighbor of v in G due to the addition of a random edge between u and v. Since the number of added random edges per node is small, it is unlikely that another low-degree neighbor of u also got a random edge added between itself and v. Hence, it is likely that u is isolated and becomes a helper node which dominates the high-degree node. On the other hand, if there are not too many low-degree vertices, and hence not too many helpers, then the analysis shows that √ most of the remaining vertices are high-degree and can be partitioned into components of O( log n) diameter (which can be used to solve MIS by gathering). Lower Bound. Our lower bound (Theorem 5.1) shows that, when p ≤ (1/2 − δ) ln n/n for a fixed δ ∈ (0, 1/2], any randomized LOCAL algorithm that computes an MIS of G = G ∪ G(n, p) with constant positive success probability for every n-node graph G requires Ω(ln n/ ln ln n) rounds. This holds even if the algorithm can distinguish original edges from added edges. We prove this by reducing MIS on an arbitrary input graph H with h nodes to MIS on G, where n is polynomially related to h. This allows us to leverage lower bounds that apply to MIS in hard (non-smoothed) instances (such as that of [22]) to derive lower bounds for MIS in the smoothed setting. The construction of G from H proceeds as follows. We replace each node u ∈ H with a clique Cu of size k, called its replacement clique. For every edge (u, v) ∈ E(H), we add edges that form a complete bipartite graph between Cu and Cv . We then add isolated padding nodes to obtain G, and smooth G to obtain G = G ∪ G(n, p). In order to leverage the reduction to prove our lower bound, we must ensure that the reduction (i) preserves the validity of the projected solution (the MIS on G projected back to the input graph H) and (ii) the running time. The first challenge is preserving maximality (for the projection). Given an MIS I of G, we select u ∈ H exactly when I contains a node of Cu . Independence follows from the edges between replacement cliques. However, selected padding nodes may dominate clique nodes without providing selected neighbors in H, so maximality does not follow automatically. We overcome this using protected nodes, whose neighborhoods are unchanged by smoothing. Choosing k = Θ(enp ln h) with 7

a sufficiently large constant factor ensures that every replacement clique contains a protected node with probability 1 − o(1) (Lemma 5.2). If an unselected node of H had no selected neighbor, the protected node in its clique would neither be selected nor have a selected neighbor in G, contradicting maximality of I. Thus every MIS of G projects to an MIS of H on this event (Lemma 5.3). The second challenge is preserving the running time. Each node u ∈ H can simulate its clique Cu locally, and communication between adjacent cliques can use the corresponding edge of H. Random edges can disrupt this simulation by connecting virtual nodes whose simulators are not adjacent in H. We first rule out added edges between clique nodes with probability 1 − o(1) (Lemma 5.4). This alone is insufficient: paths through padding nodes can also create communication between different local simulations, even when these paths do not shorten distances between the original nodes. We therefore analyze the radius-(T + 2) neighborhoods of all clique nodes after removing all edges between clique nodes, where T is the running time of the algorithm being simulated. Each node of H independently generates virtual trees for its clique nodes using a random process. The main difficulty is ensuring that these locally generated trees all represent the relevant neighborhoods of a genuine smoothed graph. For T < ε ln n/ ln ln n, where ε > 0 is sufficiently small, the total number of virtual nodes is at most a cutoff s with probability 1 − o(1), where ps2 = o(1) (Lemma 5.5). In the coupling argument described below, this cutoff lets us bound the probability of repeated IDs or unwanted edges before the cutoff by O(ps2 ) = o(1). We then construct a coupling under which, with probability 1 − o(1), all virtual trees are identical to their corresponding neighborhoods, including node IDs. These neighborhoods are pairwise disjoint and have no edges between them in the graph obtained after removing all edges between clique nodes (Lemma 5.6). There is a tension between the two parts of the proof: larger cliques make the existence of protected nodes more likely, but also increase the number of trees and the chance of interactions between them. The slack provided by δ allows both requirements to hold simultaneously. Still, it should be noted that choosing the correct parameters to satisfy both properties is non-trivial. Consequently, each node of H can locally simulate its clique and attached trees, while combining all messages between adjacent cliques into one LOCAL message over the corresponding edge of H. A T -round algorithm on G with success probability σ therefore gives a T + O(1)-round algorithm on H with success probability σ − o(1) (Lemma 5.7). Since ln h/ ln ln h = Θ(ln n/ ln ln n), the lower bound of Khoury and Schild [22] yields the claimed bound. The same construction also handles random deletions: all original edges lie among the clique nodes, and thus the probability that any of them is deleted is o(1) (Theorem 5.8).

1.8

Additional Related Work

Smoothed analysis was first used in the context of the simplex algorithm [32]. Subsequently, it has been applied to various algorithmic problems in the sequential setting (see, e.g., [33] for a survey and further references). Recent examples of smoothed analysis include online algorithms [20] and graph isomorphism [15, 3]. Here we focus on prior work on smoothed analysis for distributed algorithms. To the best of our knowledge, the two main works on smoothed analysis of distributed algorithms are due to Dinitz, Fineman, Gilbert, and Newport [13, 14] on smoothed analysis of dynamic networks and Chatterjee, Pandurangan, and Pham [10] on smoothed analysis of the distributed minimum spanning tree (MST) problem. The works of [13, 14] consider a dynamic graph H = G1 , G2 , . . . that describes an evolving network topology, where Gi is the graph at round i. Graphs in H share the same node set and are connected, but the edges can change arbitrarily from one round to the next. They define
a smoothing model for a dynamic graph parameterized by a smoothing factor k ∈ {1, 2, . . . , n2 }. 8

To k-smooth a dynamic graph H is to replace each static graph Gi in H with a smoothed graph G′i sampled uniformly from the space of connected graphs that are within edit distance k of Gi . They study three fundamental problems with strong lower bounds in dynamic network models: flooding, random walks, and aggregation. For each problem, they study the robustness/fragility of the existing bounds and show how they improve under increasing amounts of smoothing. The work of [10] introduced smoothed analysis in the context of distributed graph algorithms. Their smoothing model is somewhat different from what is considered here and in other papers such as [3]. It must be noted that MST is a weighted graph problem and it can be shown that smoothing the weights by adding a small amount of random noise (à la Spielman and Teng [32]) √ does not overcome the worst-case bound of Ω̃(D + n) rounds for distributed MST. Instead, they consider a smoothing model where, in each round of the distributed algorithm, every node can add an edge to another random node (chosen uniformly at random from V ) with probability p(n) (smoothing parameter). Thus, a key difference in this model is that each node knows the random edges added, which is crucial for the analysis. The added random edges (with weight ∞), once they are added, can be used (only) for communication and do not affect the MST of the base graph G. They show upper and lower bounds on the time complexity of distributed MST in the above √ smoothing model that shows how the worst-case barrier√of D + n can be overcome. In particular, √ they show that MST can be solved in Õ(min{ √ 1 2O( log n) , D + n}) rounds. They also show a p(n) √ lower bound of Ω̃(min{ √ 1 , D + n}). p(n)

2

Preliminaries

The base graph G is a fixed simple graph on a vertex set V with |V | = n. Every pair of vertices that is not an edge of G is added to a set R independently with probability p=

λ , n

where

λ = β ln n

for a constant β ≥ 1; the value of β is fixed in Section 4. The smoothed graph is G = G ∪ R. The algorithm sees only G: it knows neither G nor which edges of G are random. We call the edges of G base edges and the edges of R random edges. The vertices communicate in the LOCAL model over G, and the goal is to compute a maximal independent set (MIS) of G. A set I ⊆ V is an MIS of G if no two vertices of I are adjacent in G and every vertex of V lies in the closed neighborhood NG [I]. We also use the degree scale j √ k B0 = e ln n . An event holds with high probability (w.h.p.) if it holds with probability at least 1 − n−c , where c > 0 is an arbitrary fixed constant. Notation. All logarithms are natural. For a graph F , by abuse of notation, we use u ∈ F to refer to u being a node of F and (u, v) ∈ E(F ) to refer to the edge (u, v) present in the graph F . Furthermore, for a graph F , a vertex v and a vertex set Q of F , we write degF (v) for the number of neighbors of v in F , NF (v) for the set of these neighbors, which we also call the F S neighbors of v, and NF [v] = NF (v) ∪ {v}. For a set Q, we write NF [Q] = v∈Q NF [v]. For vertices u, v of F , distF (u, v) is the length of a shortest path from u to v in F (∞ if there is none), and distF (u, Q) = miny∈Q distF (u, y). Finally, NF2 [Q] = {v ∈ V (F ) : distF (v, Q) ≤ 2} 9

is the set of vertices within distance two of Q in F . Fact 2.1 (Chernoff Bounds [28]). Let X be a sum of independent Bernoulli variables. (F1) If E[X] ≤ µ, then P[X > 2µ] ≤ e−µ/3 . 2

(F2) If E[X] ≥ µ and 0 < δ < 1, then P[X ≤ (1−δ)µ] ≤ e−δ µ/2 ; in particular P[X < µ/2] ≤ e−µ/8 . Diameter of random graphs. For an integer N ≥ 1 and q ∈ [0, 1], let G(N, q) denote the random graph on N vertices in which every pair of vertices is an edge independently with probability q. Chung and Lu [11] showed that if N q → ∞, then diam(G(N, q)) = (1 + o(1)) ln N/ ln(N q) with probability 1 − o(1). For our analysis, we need an upper bound of the same order whose failure probability is explicit and exponentially small in N q. The following lemma provides it; its proof is the standard expansion argument, which we include in Appendix A. Lemma 2.2. There is an absolute constant c′ ≥ 1 such that the following holds. Let 0 < q ≤ 1/2 and ν = N q ≥ c′ (ln N + 1). Then X ∼ G(N, q) satisfies   ′ P diam(X) > 2r + 1 ≤ 3e−ν/c ,

 where r =

 ln N + 1. ln(ν/8)

MIS on graphs of bounded degree. We use the following MIS algorithm as a black box in our result. This result was reproved in Theorem 7 of [19] and also appeared previously in [17] and [16]. Proposition 2.3 (Theorem 7 of [19]). For any n-vertex graph H with maximum degree ∆, there exists a randomized LOCAL algorithm that computes an MIS with high probability in O(log ∆) + 3 e O(log log n) rounds. A Gathering Primitive. Let H be a graph whose vertices have distinct identifiers and communicate in the LOCAL model over H. Let A ⊆ V (H) be a set of vertices such that every vertex knows whether it lies in A, and for v ∈ A, let Cv denote the component of H[A] containing v. We use a deterministic primitive in which every v ∈ A learns Cv whenever every vertex of Cv is within distance r of v in H, within r + 1 rounds. The algorithm relays messages through all vertices and edges of H, including those outside A. The algorithm also uses the fact that LOCAL messages have unbounded size. It must also be safe when this distance condition fails: v checks that what it has learned is complete and, if not, reports failure, so it never outputs an incorrect graph. Lemma 2.4 (Gathering). Let H be a graph and A ⊆ V (H) be a set of vertices such that every vertex knows whether it lies in A, and let r ≥ 1 be an integer. The procedure Gather(H, A, r) below is deterministic and takes r + 1 rounds on H. At its end, every v ∈ A outputs either a graph or the symbol ⊥, and: (i) if v outputs a graph, this graph is Cv ; (ii) if every vertex of Cv is within distance r of v in H, then v outputs Cv . 10

The procedure Gather(H, A, r). In one round, every vertex v ∈ A learns which of its neighbors lie in A, and forms its adjacency list
adjA (v) = ID(v), {ID(u) : u ∈ NH (v) ∩ A} . (1) Collect. Every v ∈ A sends adjA (v). For r rounds, every vertex of H, in A or not, forwards all lists it has received. (2) Check. For v ∈ A, let Mv be the graph whose vertices are the identifiers with a list received by v, including its own, and whose edges are the pairs reported by these lists. Let Kv be the component of Mv containing v, and let Lv be the set of lists of the vertices of Kv . Note that the graph Mv may contain vertices of other components of H[A], since lists travel through all of H; but no list reports an edge of H[A] between different components, so these vertices are not in Kv . Every identifier in the lists belongs to a vertex of A, since a list reports only neighbors in A. The set Lv is closed if every vertex that appears as a neighbor in a list of Lv also has its own list in Lv . (3) Output. If Lv is closed, v outputs Kv . Otherwise, v outputs ⊥. Proof of Lemma 2.4. The procedure is deterministic and requires r + 1 rounds: one round to create the lists, followed by r rounds of Collect. The Check and Output steps are local, and no step involves randomness. (i) Let v ∈ A be such that Lv is closed. Every list is the true adjacency list in H[A] of a vertex of A, so Kv is a connected subgraph of H[A] containing v, and hence a subgraph of Cv . By definition of Lv being closed, every neighbor in H[A] of a vertex of Kv has its list in Lv , so it is a vertex of Kv , and the edge between them is reported. Following edges of H[A] from v therefore never leaves Kv , so Kv = Cv . (ii) Assume that every vertex of Cv is within distance r of v in H. A list travels one edge per round, so v receives the list of every vertex of Cv during the Collect step. These lists report all edges of Cv , so Cv is a connected subgraph of Mv containing v. No list reports an edge from Cv to a vertex outside Cv , so Kv = Cv . The lists of Lv name only vertices of Cv , all of which have their lists in Lv . So Lv is closed, and v outputs Cv .

3

Structural Properties of Smoothed Graphs

This section proves two properties (that do not depend on any algorithm) of the smoothed graph G. The first (Section 3.1) shows that if the two-hop neighborhood Z of a set Q of vertices of large degree in a subgraph of the base graph G has many vertices, then its diameter in G, that is diam(G[Z]), √ is O( ln n), with very high probability. The second (Section 3.2) shows that, in a fixed graph of √ O( ln n) , all but a constant number of the vertices of a small random sample are maximum degree e pairwise at distance greater than two, this makes their outcomes in the algorithm independent. Section 4 uses the first property to show that the high-degree vertices that the algorithm does not handle in its first step are pairwise close in G, and the second to make the success events of different helpers independent.

3.1

Smoothed Diameter of Large Two-Hop Neighborhoods

Let F be a fixed subgraph of the base graph and let Q be a set of vertices of large degree in F , called seeds. The two-hop neighborhood Z = NF2 [Q] may have large diameter in F , or even be 11

disconnected, since different seeds can be far apart or even lie in different components√of F . We show that if Z has many vertices, then the random edges reduce its diameter in G to O( ln n). All sets in this subsection are fixed before the random edges are drawn, so the only randomness is R. Lemma 3.1 (Smoothed diameter of a large two-hop neighborhood). Let F be a fixed subgraph of √ ln n ≤ s ≤ B , and let Q ⊆ V (F ) be a fixed set of seeds with 0.49 G, let s be an integer with e 0 √ degF (v) > s for every v ∈ Q. If Z = NF2 [Q] satisfies |Z| ≥ n/ s, then, for all sufficiently large n (depending only on β), h i  λ√s  √ P diam(G[Z]) > 200 ln n ≤ 3 exp − ′ , 4c where c′ is the constant of Lemma 2.2. In particular, the right-hand side is smaller than every fixed inverse polynomial in n. The idea is to partition Z into parts of between s and 2s vertices, such that any two vertices of the same part are joined by a path of length at most eight in F [Z] (Lemma 3.2). We use these parts in the proof of Lemma 3.1 to create a quotient graph Γ: its vertices are the parts, and two vertices (representing two parts) are adjacent if G has an edge between them. Two parts span at least s2 vertex pairs, so they are adjacent in Γ with probability at least η0 = λs2 /(2n). This probability is small, but there are √m ≥ |Z|/(2s) parts, so Γ contains an Erdős–Rényi graph G(m, η0 ) for which √ √ mη0 ≥ λ s/4 = eΩ( ln n) . By Lemma 2.2, its diameter is O(ln m/ ln(mη0 )) = O( ln n). Finally, a short path in Γ lifts to a short path in G[Z], which implies the diameter upper bound on G[Z]. Throughout the following, z = |Z|. Lemma 3.2 (A balanced partition). Let F be a graph, let s ≥ 1 be an integer, and let Q ⊆ V (F ) be a nonempty set of vertices called seeds with degF (v) > s for every v ∈ Q. Let Z = NF2 [Q] and z = |Z|. Then Z can be partitioned into m sets W1 , . . . , Wm , called parts, such that (i) s ≤ |Wi | ≤ 2s for every i, and hence z/(2s) ≤ m ≤ z/s; and (ii) any two vertices of the same part are joined by a path of length at most eight in F [Z]. Proof. Figure 1 illustrates the construction. Using the seed vertices, let us build cores, each consisting of a seed, called its center, and s of its F -neighbors. Fix an arbitrary order c1 , . . . , c|Q| of the seeds, and process them in this order. When ci is processed, if ci lies in no core built so far and at least s of its F -neighbors lie in no core built so far, we build a core consisting of ci and s such neighbors; otherwise we build nothing. By construction, the cores are pairwise disjoint. Let U be the set of all vertices of the cores. At least one core is built, since c1 has more than s F -neighbors and no core exists before it is processed. Moreover, U ⊆ Z, since every vertex of a core is within distance one of its center. Now, we show that every vertex of Z is within distance three of U in F [Z]. Let y be a seed with y ∈ / U . In this case, either y is connected directly to the seed vertex of an already created core (this contradicts y ∈ / U ), or y has fewer than s neighbors in F \ U while it was processed. As y has more than s F -neighbors, at least one of them lies in U . Now, as y ∈ Z, we can say that y is at distance one from U in F [Z]. This implies that every seed vertex of Q is at distance at most one from U in F [Z]. Now let x ∈ Z. Then, by definition of Z, x is connected to at least one seed vertex within distance two in F [Z]. So, it has distance at most three from U in F [Z]. Clusters. Next, we form disjoint clusters of the vertices of Z, by assigning a center to every vertex of Z. If x ∈ U , then x belongs to exactly one core, and we assign to x the center of that core. Otherwise, x is joined to U by a path of length at most three in F [Z]. Let u ∈ U be a vertex 12

closest to x in F [Z], breaking ties arbitrarily, and assign to x the center of u. For each center c, the vertices assigned to c form the cluster of c. The subgraph of F induced by a cluster need not be connected, since a shortest path from x to u may pass through vertices of other clusters. We only need the following properties. Every vertex of Z is assigned exactly one center, so the clusters are pairwise disjoint and cover Z. Every vertex x of a cluster is joined to its center by a path of length at most four in F [Z]: a path of length at most three from x to u, followed by the edge from u to its center if u is not the center itself. Finally, each cluster contains its core, and hence at least s + 1 vertices. Finally, we split the clusters into parts. Split a cluster with w ≥ s+1 vertices into g = ⌊w/s⌋ ≥ 1 parts whose sizes differ by at most one, so each size is ⌊w/g⌋ or ⌈w/g⌉. Since g ≤ w/s, each size is at least s. Since w < (g + 1)s ≤ 2gs, each size is at most 2s. This proves (i); the bounds on m follow since the part sizes sum to z. Two vertices of one part lie in the same cluster, and joining their paths to its center gives a path of length at most eight in F [Z]. This proves (ii). (a) cores and clusters (s = 2)

(b) splitting the clusters into parts

y c

c

c′

Seeds are filled, and the cores, with centers c and c′ , are drawn thick. Arrows show shortest paths to the cores, and the two clusters are shaded.

c′

Colors show the parts. A cluster of w vertices is split into ⌊w/s⌋ parts, each of size between s and 2s.

Figure 1: The construction in the proof of Lemma 3.2, with s = 2. (a) Cores are built greedily, i.e., each core consists of a seed, called its center, together with s of its F -neighbors. The seed y lies in no core, but it has an F -neighbor in a core. Every other vertex of Z is assigned the center of a closest core vertex, and the arrows show shortest paths to the cores. The vertices assigned to the same center form a cluster, and each of them is within distance four of its center in F [Z]. (b) Each cluster is split into parts of size between s and 2s. The left cluster has 6 vertices and is split into 3 parts of size 2; the right cluster has 5 vertices and is split into parts of sizes 2 and 3. A part need not be connected, but any two of its vertices are joined, through the center of their cluster, by a path of length at most eight in F [Z]. Like the clusters, a part need not be connected; (ii) only says that its vertices are close in F [Z]. The parts depend only on F and are used only in the analysis. We are now ready to prove Lemma 3.1. √ Proof of Lemma 3.1. Since z ≥ n/ s > 0 and Z = NF2 [Q], we have Q ̸= ∅. Fix the parts W1 , . . . , Wm of Lemma 3.2, and let Γ be their quotient graph: its vertices are 1, . . . , m, and i ̸= j are adjacent if G has an edge between Wi and Wj . The quotient graph contains G(m, η0 ). Since s ≤ B0 , we have ps2 ≤ λB02 /n → 0; so for large n, ξ := ps2 ≤ 1. Let η0 = ξ/2 = λs2 /(2n). If G has an edge between Wi and Wj , the parts are adjacent. Otherwise, all |Wi | |Wj | ≥ s2 pairs between them are missing from G and enter R 13

2

independently, so the parts are adjacent with probability at least 1 − (1 − p)s ≥ 1 − e−ξ ≥ ξ/2 = η0 , using e−ξ ≤ 1 − ξ/2 for 0 ≤ ξ ≤ 1. Different pairs of parts use disjoint sets of vertex pairs, so these adjacencies are independent. Hence we may realize Γ using independent random numbers υij , each uniform on [0, 1], by declaring i, j adjacent when υij ≤ P[i, j adjacent]. Let X be the graph on {1, . . . , m} in which i, j are adjacent when υij ≤ η0 . Then X ∼ G(m, η0 ), and X ⊆ Γ since η0 ≤ P[i, j adjacent]. Hence diam(Γ) ≤ diam(X). Bounding the diameter of X. We apply Lemma 2.2 with N = m and q = η0 ≤ 1/2. Using √ m ≥ z/(2s) and z ≥ n/ s, √ z λs2 λ s ln n 0.245√ln n ν := mη0 ≥ · ≥ ≥ e , 2s 2n 4 4 since λ ≥ ln n. This is at least c′ (ln n+1) ≥ c′ (ln m+1) for large n. So, with r = ⌈ln m/ ln(ν/8)⌉+1, √ ′ we get diam(X) ≤ 2r + 1 except with probability 3e−ν/c ≤ 3 exp(−λ s/(4c′ )). Now since s ≥ √ e0.49 ln n and λ ≥ ln n, √ √ ν ln ≥ 12 ln s + ln λ − ln 32 ≥ 0.245 ln n + ln ln n − ln 32 ≥ 0.24 ln n 8 √ √ for large n. With ln m ≤ ln n, this gives r ≤ ln n/0.24 + 2, so 2r + 1 ≤ 8.4 ln n + 5. Putting everything together. We now bound the diameter of G[Z]. Suppose that diam(Γ) ≤ 2r + 1, and let u, v ∈ Z. Take a shortest path i0 , . . . , iτ in Γ from the part of u to the part of v, so τ ≤ 2r + 1, and for each j an edge xj yj of G with xj ∈ Wij−1 and yj ∈ Wij . With y0 = u and xτ +1 = v, the vertices yj and xj+1 lie in the same part, so by Lemma 3.2(ii) they are joined by a path of length at most eight in F [Z]. Concatenating these paths with the edges xj yj gives a walk from u to v in G[Z] of length at most √ √ 8(τ + 1) + τ ≤ 9(2r + 1) + 8 ≤ 75.6 ln n + 53 < 200 ln n. √ So √ diam(Γ) ≤ 2r + 1 implies diam(G[Z]) ≤ 200 ln n. Since X ⊆ Γ, the event diam(G[Z]) > 200 ln n therefore implies diam(X) > 2r + 1. By Lemma 2.2, applied to X ∼ G(m, η0 ) in the √ ′ previous paragraph, this has probability at most 3e−ν/c ≤ 3 exp(−λ s/(4c′ )). All conditions “for √ √ 0.245 ln n large n” above involve only n and β. Finally, λ s ≥ ln n · e , so this bound is smaller than every fixed inverse polynomial in n. Remark 3.3. Partitioning into clusters around high-degree vertices and then analyzing a random quotient graph is adapted from the diameter arguments of Aigner-Horev, Hefetz and Krivelevich [1]. Lemma 3.1 extends the idea to two-hop neighborhoods of high-degree seeds in an arbitrary fixed subgraph, with explicit failure probabilities.

3.2

Most Randomly Sampled Vertices Are Isolated

Let F0 be a fixed graph with V (F0 ) ⊆ V , so that F0 has at most n vertices, and with maximum degree at most ∆ ≥ 1, and let V0 ⊆ V (F0 ) be fixed. We show that, for a fixed constant q, fewer than q sampled vertices have another sampled vertex within distance two in F0 , except with probability n−q/2+o(1) (Lemma 3.5). Definition 3.4 (Squares, isolated vertices, witnesses). The square F02 of F0 is the graph on V (F0 ) in which two distinct vertices u, v are adjacent if distF0 (u, v) ≤ 2. For P ⊆ V (F0 ), a vertex v ∈ P is isolated in F02 [P ] if distF0 (u, v) > 2 for every u ∈ P \ {v}, and non-isolated otherwise. A component of a graph is trivial if it has exactly one vertex. A set W ⊆ V (F0 ) is a witness if no component of F02 [W ] is trivial. 14

By definition, a vertex of P is isolated in F02 [P ] exactly when it forms a trivial component of F02 [P ]. So the non-isolated vertices of F02 [P ] are exactly the vertices of the nontrivial components of F02 [P ]. The following lemma is the main result of this subsection. Lemma 3.5 (Few sampled vertices are close). Let F0 be a fixed graph with at most n vertices and maximum degree at most ∆ ≥ 1, and let V0 ⊆ V (F0 ) be fixed. Let 1 ≤ k ≤ n, and let B be the random set that contains each vertex of V0 independently with probability k/n. Then, for every integer q ≥ 2, 2q−1 h i  ∆4 k 2 j/2 X . P at least q vertices of B are non-isolated in F02 [B] ≤ (j + 1)j n j=q

√ In particular, if ln ∆ = O( ln n), k = O(ln n) and q is fixed, then the right-hand side is at most n−q/2+o(1) , where the o(1) term depends only on q and the implied constants, and not on F0 or V0 . We prove Lemma 3.5 by a union bound over small sets that certify the bad event. Lemma 3.6 shows that whenever at least q sampled vertices are non-isolated, the sample contains a witness of size between q and 2q − 1. Lemma 3.7 bounds the number of such witnesses. Finally, a fixed witness of size j lies entirely in the sample with probability at most (k/n)j . A union bound over all witnesses of size between q and 2q − 1 then bounds the probability that at least q sampled vertices are non-isolated by the sum in Lemma 3.5. Lemma 3.6 (A bad sample contains a small witness). Let P ⊆ V (F0 ), and let q ≥ 2 be an integer. If at least q vertices of P are non-isolated in F02 [P ], then P contains a witness W with q ≤ |W | ≤ 2q − 1. Proof. The non-isolated vertices of F02 [P ] are the vertices of its nontrivial components, and there are at least q of them. We distinguish two cases. Some nontrivial component K of F02 [P ] has at least q vertices. Run a breadth-first search in K from any vertex, and let W be the set of the first q vertices it visits. Every vertex of W other than the first is adjacent in F02 to its BFS parent, which was visited earlier and hence lies in W . So F02 [W ] is connected. Since |W | = q ≥ 2, its only component is nontrivial, and W is a witness with |W | = q. Every nontrivial component of F02 [P ] has fewer than q vertices. Starting from W = ∅, add whole nontrivial components of F02 [P ] to W , one at a time, and stop as soon as |W | ≥ q. This happens, since these components together contain at least q vertices. Just before the last addition, |W | ≤ q − 1, and the last component added has at most q − 1 vertices, so |W | ≤ 2q − 2. There are no edges of F02 between different components of F02 [P ], so the components of F02 [W ] are exactly the components added. Each of them is nontrivial, so W is a witness. In both cases W ⊆ P and q ≤ |W | ≤ 2q − 1. Lemma 3.7 (Counting witnesses). Let F0 be a graph with at most n vertices and maximum degree at most ∆ ≥ 1, and let j ≥ 1. The number of witnesses W ⊆ V (F0 ) with |W | = j is at most (j + 1)j nj/2 ∆2j . Proof. A witness is defined through F02 : every vertex of a witness W has another vertex of W within distance two in F0 , but not necessarily adjacent to it in F0 . So, once one vertex of W is known, each vertex of W linked to it lies among its neighbors in F02 , not only among its neighbors in F0 . 15

A vertex of F0 has at most ∆ neighbors, and at most ∆(∆ − 1) vertices at distance exactly two, each reached through one of these neighbors. So every vertex has at most ∆ + ∆(∆ − 1) = ∆2 neighbors in F02 . Let us now fix a witness W with |W | = j. In each component of F02 [W ], choose a spanning tree and a root. These trees form a spanning forest of F02 [W ]. Each tree has at least two vertices, since W is a witness, so the number ρ of trees satisfies ρ ≤ j/2. Labels. Now, let us list the trees one after another, and list the vertices of each tree in breadthfirst order from its root. This gives labels 1, . . . , j to the vertices of W such that the parent of every non-root vertex has a smaller label. Record the forest by the parent map σ : {1, . . . , j} → {0, 1, . . . , j} , where σ(i) = 0 if vertex i is a root, and σ(i) is the label of its parent otherwise. Every parent map obtained in this way satisfies σ(i) < i whenever σ(i) ̸= 0, and σ(i) = 0 for at most j/2 labels i. We call a map with these two properties admissible. Encoding W . The witness W is determined by its admissible parent map σ together with the sequence w1 , . . . , wj of its vertices in label order. There are at most (j + 1)j admissible maps σ, since each of the j labels is sent to one of j + 1 values. Fix an admissible σ, and let ρ ≤ j/2 be its number of zeros. Choose w1 , . . . , wj in this order: • if σ(i) = 0, then wi is any vertex of F0 , so there are at most n choices; • otherwise, wi is a neighbor in F02 of wσ(i) , which is already chosen since σ(i) < i; so there are at most ∆2 choices. This gives at most nρ ∆2(j−ρ) ≤ nj/2 ∆2j sequences, using ρ ≤ j/2, n ≥ 1 and ∆ ≥ 1. Conclusion. Every witness of size j arises from at least one pair consisting of an admissible map σ and a sequence w1 , . . . , wj . Some pairs may give no witness or the same witness twice; this only increases the count. Hence there are at most (j + 1)j nj/2 ∆2j witnesses of size j. We are now ready to prove the main result of this subsection. Proof of Lemma 3.5. Suppose that at least q vertices of B are non-isolated in F02 [B]. By Lemma 3.6 with P = B, the set B contains a witness W with q ≤ |W | ≤ 2q − 1. So it suffices to bound the probability that B contains such a witness. Now, fix a witness W with |W | = j. If W ̸⊆ V0 , then W ̸⊆ B, since B ⊆ V0 . Otherwise, the j vertices of W lie in B independently, each with probability k/n, so P[W ⊆ B] ≤

 k j n

.

By Lemma 3.7, for each j there are at most (j + 1)j nj/2 ∆2j witnesses of size j. Summing over j = q, . . . , 2q − 1, P[at least q non-isolated] ≤

2q−1 X

j

(j + 1) n

j=q

j/2

∆

2j

 k j n

=

2q−1 X

(j + 1)j

j=q

 ∆4 k 2 j/2 n

j/2 2j j −j 4 2 j/2 where the last step uses √ n ∆ k n = (∆ k /n) . Now let ln ∆ = O( ln n), k = O(ln n) and q be fixed, and put y = ∆4 k 2 /n. Then √

ln ∆4 k 2 = 4 ln ∆ + 2 ln k = O ln n + O(ln ln n) = o(ln n),

16

,

and hence y ≤ n−1+o(1) . In particular, y ≤ 1 for all sufficiently large n, so y j/2 ≤ y q/2 for every j ≥ q. Moreover, (j + 1)j ≤ (2q)2q for j ≤ 2q − 1, and the sum has q terms. Since q is fixed, 2q−1 X

(j + 1)j y j/2 ≤ q (2q)2q y q/2 ≤ n−q/2+o(1) .

j=q

The o(1) terms depend only on q and the implied constants, and not on F0 or V0 .

4

√ An O( log n)-round Smoothed MIS Algorithm

This section proves that, √ for λ = β ln n with a suitable constant β, an MIS of the smoothed graph G can be computed in O( log n) rounds. The algorithm is given only G, the number n and distinct identifiers; it knows neither which edges of G are random nor the degrees in the base graph G. Theorem 4.1. For every constant c > 0, there is a constant β ≥ 1, depending only on c, such that the following holds for all sufficiently large n. Let G be any graph on n vertices, and let G be its smoothing with λ = β ln n. There is a randomized LOCAL algorithm √ that, given G, the number n, and distinct identifiers of O(log n) bits, computes an MIS of G in O( log n) rounds with probability at least 1 − n−c . The probability is over the random edges and the random bits of the algorithm. The constant β grows with c, i.e., a smaller failure probability requires more random edges. We describe the algorithm in Section 4.1 and prove Theorem 4.1 in Section 4.2. In its second step, the algorithm uses the gathering primitive of Lemma 2.4.

4.1

Algorithm Description

The algorithm is given G, the number n, and distinct identifiers. The constant β of Theorem 4.1 is part of the algorithm: with λ = β ln n, every vertex computes the following three values: B = B0 + 2λ,

θ=

⌈λ/2⌉ , λ

ℓ = 1000

l√

m ln n .

Here B is a degree threshold, θ is a marking probability, and ℓ is a round budget. For λ > 2 we have ⌈λ/2⌉ < λ, so θ < 1 is a valid probability. Definition 4.2 (High and low vertices, Vhi and Vlo ). A vertex v is high if degG (v) > B, and low otherwise. We write Vhi to denote the set of high vertices and Vlo to denote the set of low vertices. Given a graph √ G, the output of the algorithm should be a maximal independent set, I, of G. Since√ log B = O( ln n), Proposition 2.3 computes an MIS of a graph of maximum degree at most B in O( ln n) rounds. So the algorithm first computes an independent set that, w.h.p., dominates all high vertices. The low vertices that this set does not dominate induce a subgraph of G of maximum degree at most B, and the algorithm runs Proposition 2.3 on it. Description. Algorithm 1 gives the algorithm, and Figure 2 illustrates it. After a set-up round, the algorithm has three steps, and each step adds an independent set to the output: S, J and K, respectively. The output is I = S ∪ J ∪ K. Set-up. Every vertex tells its neighbors whether it is high or low. Step 1 (helpers). Every high vertex marks each of its edges to a low neighbor independently with probability θ, and tells that neighbor. A low vertex with at least one marked edge is a candidate. 17

A candidate joins the set S if none of its neighbors is a candidate. The vertices of S are called helpers. Step 2 (gathering). A high vertex with no neighbor in S is active, and A = Vhi \ NG [S] is the set of active vertices. All vertices of G run Gather(G, A, ℓ) (Lemma 2.4), so that every active vertex v either learns its component Cv of G[A] or outputs ⊥. Fix a deterministic rule that maps every graph C with vertex identifiers to an MIS JC of C, for example the greedy MIS in increasing order of identifier. If v learns Cv , it computes JCv and joins J if v ∈ JCv . If v outputs ⊥, it does not join J. Step 3 (completion). Let Vrest = Vlo \ NG [S ∪ J] be the set of low vertices with no neighbor in S ∪ J. Every low vertex has degree at most B in G, so G[Vrest ] has maximum degree at most B. The algorithm of Proposition 2.3 is run on G[Vrest ] with ∆ = B, and its output is K. Remark 4.3 (The round budget ℓ). All vertices run Gather for the same number ℓ + 1 of rounds, fixed in advance, so that all of them start Step 3 together. Lemma 4.5 shows that, w.h.p., either A = ∅ or all active vertices are pairwise to l√within m distance ℓ in G, so that Lemma 2.4(ii) applies √ every active vertex. The value ℓ = 1000 ln n is chosen so that it exceeds the distance 200 ln n+4 that arises in the proofs of Lemmas 4.7 and 4.8. Algorithm 1 Smoothed MIS Require: the graph G, the number n, distinct identifiers. Set-up:  classify by degree 1: Vhi ← v : degG (v) > B , Vlo ← V \ Vhi ; every vertex tells its neighbors its class. Step 1: helpers 2: for all edges uv of G with u ∈ Vhi , v ∈ Vlo do 3: u marks uv independently with probability θ and tells v. 4: end for 5: Y ← {v ∈ Vlo : v has a marked incident edge} ▷ candidates 6: S ← {v ∈ Y : v has no neighbor in Y } ▷ helpers Step 2: gather and solve the remaining high vertices 7: A ← Vhi \ NG [S] ▷ active vertices 8: Run Gather(G, A, ℓ) ▷ Lemma 2.4 9: J ← {v ∈ A : v outputs a graph C and v ∈ JC } ▷ fixed MIS rule on each component Step 3: finish the low vertices 10: Vrest ← Vlo \ NG [S ∪ J] 11: Run the algorithm of Proposition 2.3 with ∆ = B on G[Vrest ]; let K be its output. 12: return I = S ∪ J ∪ K

4.2

Algorithm Analysis

In this subsection, we prove Theorem 4.1. Throughout, the base graph G is fixed, and the randomness comes from the random edges R and the random bits of the algorithm. If every high vertex is dominated by S ∪ J, then Step 3 completes S ∪ J to an MIS of G, using the algorithm of Proposition 2.3 on the remaining low vertices. So the main question is whether S ∪ J dominates all high vertices. We first show, in Lemma 4.4 below, that the set J computed in Step 2 is independent, and that it dominates every active vertex whenever the active vertices are pairwise within distance ℓ in G. 18

(a) Set-up: classify

(b) Step 1: helpers

a

c

red: marked edges; orange: candidates; S = {a}; grey: dominated by S

filled: high (degG > B); hollow: low

(c) Step 2: gather

h3

b

(d) Step 3: complete A h5 f

dashed box: active set A (thick: G[A]); J = {h3 , h5 }, an MIS of G[A]

d

thick: G[Vrest ]; K = {f, d}; double circles: I = S ∪ J ∪ K

Figure 2: Algorithm 1 on a small example. Filled vertices are high and hollow vertices are low; vertices of the output I are drawn with a double circle. (a) The set-up splits the vertices into Vhi and Vlo . (b) Step 1: the high vertices mark some of their edges to low neighbors (red), and the low endpoints a, b, c become candidates (orange). The candidate a has no candidate neighbor, so S = {a}; the candidates b and c are adjacent, so neither joins S. The two high vertices adjacent to a are dominated by S and drawn grey from now on; they are not active. (c) Step 2: the other three high vertices form the active set A (dashed box), and G[A] is the path drawn thick. Every active vertex gathers this component, and the vertices compute the same MIS J = {h3 , h5 } of it. (d) Step 3: the low vertices with no neighbor in S ∪ J form Vrest , and G[Vrest ] (thick) has maximum degree at most B. Proposition 2.3 computes an MIS K = {f, d} of it, and I = S ∪ J ∪ K.

19

This reduces the analysis to proving that the following condition holds on the active vertices: (1)

A = ∅,

or all vertices of A are pairwise within distance ℓ in G.

Lemma 4.5 states that condition (1) holds w.h.p., for every base graph, and Section 4.2.1 proves it. This is the most involved part of the analysis. It splits the base graphs into three cases, using sets defined from G alone. In two of the cases, Lemma 3.1 shows that all active vertices are close together. In the third case, we use the random choice of the helpers in Step 1, together with Lemma 3.5, to show that the helpers dominate every high vertex, so that no vertex is active. Finally, Section 4.2.2 combines these results and proves Theorem 4.1. Parameters of the analysis. Fix c > 0. Let a ≥ 48(c + 3) be a constant and q ≥ 2c + 7 an integer, also put β = 2a, so that λ = 2a ln n. Let k = θλ = ⌈λ/2⌉ = ⌈a ln n⌉ . Lemma 4.4. The set J computed in Step 2 is independent in G. If condition (1) holds, then A ⊆ NG [J]. Proof. We apply Lemma 2.4 with H = G, A = A and r = ℓ. For v ∈ A, let Cv be the component of G[A] containing v. Independence. Let u, w ∈ J be adjacent in G. Then u, w ∈ A lie in the same component C of G[A]. Both output a graph (i.e., they do not fail), so by Lemma 2.4(i) both output C. Both apply the same deterministic rule to C, so they compute the same MIS JC of C, and both lie in JC . This contradicts the independence of JC . Domination. If A = ∅, there is nothing to show. Otherwise, let v ∈ A. Since condition (1) holds and Cv ⊆ A, every vertex of Cv is within distance ℓ of v in G. By Lemma 2.4(ii), v outputs Cv , and it joins J if and only if v ∈ JCv . Hence J ∩ C = JC for every component C of G[A]. Since JC is an MIS of C, every vertex of C lies in NG [J]. So A ⊆ NG [J]. By Lemma 4.4, the set J dominates A whenever condition (1) holds. The next lemma shows that this happens w.h.p.; we prove it in Section 4.2.1. Lemma 4.5. For every base graph G and all sufficiently large n, condition (1) holds with probability at least 1 − n−c−1 . 4.2.1

Proof of Lemma 4.5

The analysis splits the base graphs into cases, using sets defined from G alone. These sets are fixed before the random edges are drawn, and the algorithm never computes them. Let H0 = {v : degG (v) > B0 } , X0 = NG (H0 ) ∩ L0 ,

L0 = V \ H0 , ZH = NG2 [H0 ],

M = |H0 | , zH = |ZH | .

We call the vertices of H0 and L0 base-high and base-low. Thus X0 is the set of base-low vertices with a base edge to H0 , and H0 ∪ X0 ⊆ ZH . In contrast, the sets Vhi and Vlo of high and low vertices (Section 4.1) are defined by the degrees in G, and they depend on the random edges. The next lemma relates the two classifications. Lemma 4.6 (Few random edges per vertex). Let E be the event that every vertex has at most 2λ incident edges in R. Then E fails with probability at most ne−λ/3 = n1−β/3 . Moreover, if E holds, we have L0 ⊆ Vlo , and hence A ⊆ Vhi ⊆ H0 . 20

Proof. The failure probability. Fix a vertex v. The number of edges of R incident to v is a sum of at most n − 1 independent indicators, one for each vertex u ̸= v with uv ∈ / E(G), each equal to 1 with probability p = λ/n. So its mean is at most (n − 1)λ/n ≤ λ. By Fact 2.1(F1) with µ = λ, it exceeds 2λ with probability at most e−λ/3 . The event E fails only if this happens for some vertex, so a union bound over the n vertices shows that E fails with probability at most ne−λ/3 = n · n−β/3 = n1−β/3 , using λ = β ln n. The inclusions when E holds. Assume that E holds, and let v ∈ L0 . Then v has at most B0 incident base edges, since v ∈ / H0 , and at most 2λ incident random edges, by E. So degG (v) ≤ B0 + 2λ = B, and v ∈ Vlo . This shows L0 ⊆ Vlo . Since Vhi = V \ Vlo and H0 = V \ L0 , it follows that Vhi ⊆ H0 . Finally, A ⊆ Vhi by the definition of A. If M = 0, then A = ∅ whenever E holds; we treat this case in the proof of Lemma 4.5 at the end of this subsection. Otherwise zH ≥ B0 + 1, since a vertex of H0 has more√than B0 neighbors in G. We distinguish three cases, determined by G alone. Case (1) is zH ≥ n/ B 0 . Otherwise, we define below √ a degree threshold t and a√set ZQ of vertices in G[L0 ], and let zQ = |ZQ |; Case (2a) is zQ ≥ n/ t, and Case (2b) is zQ < n/ t. In Cases (1) and (2a), we show that all vertices of H0 , and hence, if E holds, all active vertices, are pairwise close in G. In Case (2b), we show that the helpers of Step 1 dominate every high vertex, so A = ∅. Figure 3 summarizes the cases. We use the inclusions of Lemma 4.6 in the following way only. In the proof of Lemma 4.5, each case bounds the probability that condition (1) fails by a union bound in which P[E c ] is one of the terms; the other terms are probabilities of events that do not involve E. We never condition on E, so the edges of R remain independent in all later calculations. fixed base graph G; is M = |H0 | zero? M =0 √ zH ≥ n/ B 0

M >0

compare zH√= |ZH | with n/ B 0

√ zQ ≥ n/ t

No base-high vertices A = ∅ on E (Lemma 4.6)

Case (1) ZH ⊇ H0 has small diameter in G (Lemma 4.7)

√ zH < n/ B 0

define t and Q; compare zQ √ = |ZQ | with n/ t

Case (2a) ZQ has small diameter in G, and each h ∈ H0 is within distance 2 of ZQ (Lemma 4.8)

√ zQ < n/ t

Case (2b) the helpers dominate every high vertex, so A=∅ (Lemma 4.13)

All of H0 , and hence (if E holds) all of A, are pairwise within distance ℓ in G

Figure 3: The case analysis in the proof of Lemma 4.5. Each test depends only on the base graph G, so exactly one of the four outcomes applies, and it is fixed before the random edges are drawn. In each outcome, the lemma named in the box shows that, with probability at least 1 − n−c−1 , either A = ∅ or all active vertices are pairwise within distance ℓ in G.

21

√ Case 1: zH ≥ n/ B 0 . √ Lemma 4.7 (Case (1)). If M > 0 and zH ≥ n/ B 0 , then, for all sufficiently large n, condition (1) holds with probability at least 1 − n−c−1 . Proof. All vertices in ZH are pairwise within distance ℓ in√ G. We apply Lemma 3.1 with F = G, √ 0.49 ln n Q = H0 and s = B0 . Its hypotheses hold: e√ ≤ e ln n − 1 ≤ B0 for n ≥ 3, every v ∈ H0 √ ′) 2 B /(4c −λ 0 has degG (v) > B0 , and NG [H0 ] = zH ≥ n/ B 0 . So, except with probability 3e , the √ diameter of G[Z ] is at most 200 ln n. On this event, all vertices of Z are pairwise within distance H H √ 200 ln n ≤ ℓ in G[ZH ], and hence in G, since G[ZH ] is a subgraph of G. Now, the active vertices lie in ZH . If E and the event in the previous paragraph hold, we have A ⊆ H0 by Lemma 4.6, and H0 ⊆ ZH by the definition of ZH . So, if E holds and the event of the previous paragraph, all vertices of A are pairwise within distance ℓ in G, and (1) holds. Let us now argue about the failure probability. Condition (1) can fail only if E fails, with probability at most ne−λ/3 by Lemma 4.6, or G[ZH ] has large diameter, with probability at most √ ′ 3e−λ B 0 /(4c ) by Lemma 3.1. So it fails with probability at most √

′

ne−λ/3 + 3e−λ B 0 /(4c ) . The first term equals n · e−β ln n/3 = n1−β/3 , since λ = β ln n; this is at most n−c−2 once β = 2a ≥ 3(c + 3), which holds since a is large enough depending on c. For the second term, λ = β ln n ≥ 1 √ √ √ ′) ′) −λ B /(4c − B /(4c 0 0 for n √ ≥ 3, so 3e ≤ 3e . Since B 0 grows faster than every multiple of ln n, we have B 0 /(4c′ ) ≥ (c + 2) ln n + ln 3 for all sufficiently large n, and then the second term is at most n−c−2 . Hence (1) fails with probability at most 2n−c−2 ≤ n−c−1 . √ √ Case (2): zH < n/ B 0 . In this case, H0 ⊆ ZH implies M < n/ B 0 . We now define a degree √ threshold t for the base-low part of G. We need e0.49 ln n ≤ t ≤ B0 , so that Lemma 3.1 applies with s = t in Case (2a), and t ≤ n/(16M k), which √ is used in Case (2b) to bound the failure probability of a test vertex (Lemma 4.12). Since M < n/ B 0 , all these constraints can be met. Define n j t = min B0 ,

n ko , 16M k

o n Q = v ∈ L0 : degG[L0 ] (v) > t ,

√ √ 2 and let ZQ = NG[L [Q] and zQ = |ZQ |. Since M < n/ B 0 , we have n/(16M k) > B 0 /(16k), 0] which is at least 1 for all sufficiently large n (depending on the√constant a). Using ⌊x⌋ ≥ x/2 for √ x ≥ 1, we get ⌊n/(16M k)⌋ ≥ B 0 /(32k). Together with B0 ≥ e ln n /2 and k = O(ln n), this gives, for all sufficiently large n, √ (2)

B0 ≤ t ≤ B0 , 32k

ln t ≥

1 2 ln B0 − ln(32k)

≥

1 2

√

√ ln n − O(ln ln n) ≥ 0.49 ln n.

√ √ So s = t is a valid choice in Lemma 3.1. Case (2a) is zQ ≥ n/ t, and Case (2b) is zQ < n/ t. √ Case (2a): zQ ≥ n/ t. √ √ Lemma 4.8 (Case (2a)). If M > 0, zH < n/ B 0 and zQ ≥ n/ t, then, for all sufficiently large n, condition (1) holds with probability at least 1 − n−c−1 . 22

Proof. ZQ has small diameter. We apply Lemma 3.1 with F = G[L0 ], seeds Q and s = t. Its √ ln n 0.49 ≤ t ≤ B0 by (2), every v ∈ Q has hypotheses hold: G[L0 ] is a fixed subgraph of G, e √ √ ′ 2 degG[L0 ] (v) > t, and NG[L0 ] [Q] = zQ ≥ n/ t. So, except with probability 3e−λ t/(4c ) , all vertices √ of ZQ are pairwise within distance 200 ln n in G[ZQ ], and hence in G. Every base-high vertex is close√ to ZQ . We claim that each h ∈ H0 is within distance two of ZQ in G, except with probability e−λ B 0 . This is clear if a G-neighbor of h, or a G-neighbor of such a vertex, lies in ZQ . Otherwise, fix B0 distinct G-neighbors y1 , . . . , yB0 of h. None of them lies in ZQ or has a G-neighbor in ZQ , so the B0 zQ pairs {yi , z} with z ∈ ZQ are distinct and are not edges of G. Each of them lies in R independently with probability p, and if one does, then h is within distance two of ZQ . All of them are missing with probability √

√

(1 − p)B0 zQ ≤ e−λB0 zQ /n ≤ e−λB0 / t ≤ e−λ B 0 , √ using 1 − p ≤ e−p , zQ ≥ n/ t and t ≤ B0 . A union bound over√the at most n vertices of H0 proves the claim for all h ∈ H0 at once, except with probability ne−λ B 0 . The active vertices are close. Suppose that E holds, that ZQ has small diameter, and that every base-high vertex is within distance two of ZQ . By Lemma 4.6, A ⊆ H0 . So √ any h, h′ ∈ A ′ ′ are within distance two √ of vertices z, z ∈ ZQ , respectively, and distG (z, z ) ≤ 200 ln n. Hence distG (h, h′ ) ≤ 2 + 200 ln n + 2 ≤ ℓ, and (1) holds. The failure probability. Condition (1) can fail only if one of three events fails: E, which fails with probability at most ne−λ/3 ; the event that ZQ has small diameter, which fails with probability √ ′ at most 3e−λ t/(4c ) by Lemma 3.1; and the event that every base-high vertex is within distance √ B −λ 0 by the union bound above. So, by a union two of ZQ , which fails with probability at most ne bound, (1) fails with probability at most √

√

′

ne−λ/3 + 3e−λ t/(4c ) + ne−λ B 0 . We bound each term by n−c−2 , for all sufficiently large n. The first term equals n·e−β ln n/3 = n1−β/3 , since λ = β ln n; this is at most n−c−2 once β = 2a ≥ 3(c + 3), which holds since a is large enough √ √ 1/4 √ depending on c. For the other two terms, λ ≥ 1 for n ≥ 3. By (2), t ≥ B0 / √32k, and both t √ and B 0 grow faster than every multiple of ln n, since k = O(ln n) and B0 ≥ e ln n /2. So, for all sufficiently large n, √

′

√

′

3e−λ t/(4c ) ≤ 3e− t/(4c ) ≤ n−c−2 ,

√

√

ne−λ B 0 ≤ ne− B 0 ≤ n−c−2 .

Hence (1) fails with probability at most 3n−c−2 ≤ n−c−1 , for n ≥ 3. √ Case (2b): zQ < n/ t. In this case we show that A = ∅, that is, S dominates every high vertex. Fix h ∈ H0 , and suppose that h is high. A base-low vertex v dominates h if (i) hv is a random edge that h marks in Step 1, so that v is a candidate, and (ii) no neighbor of v is a candidate, so that v ∈ S. If v is not a base neighbor of h, then v satisfies (i) with probability pθ = k/n. We proceed in two steps. • In Lemma 4.10, we show that, with probability at least 1 − 2n−c−3 , at least ⌊k/3⌋ vertices satisfy (i) and are pairwise at distance at least three in the base-low graph F0 defined below. We call them the test vertices of h. Since they are far apart, the events that they satisfy (ii) are independent. 23

• In Lemma 4.12, we show that each test vertex fails (ii) with probability at most 1/4, so all of them fail with probability at most 4−⌊k/3⌋ . If some test vertex satisfies (ii), it joins S and dominates h (Lemma 4.11). So h is dominated with high probability. The base-low graph. Let F0 = G[L0 ] be the subgraph of G induced on the base-low vertices. It contains both the base edges and the random edges inside L0 ; the former are fixed by G, so F0 is determined by G and the random edges inside L0 . Let X0+ = NF0 [X0 ] be the set of base-low vertices that lie in X0 or are adjacent in F0 to a vertex of X0 . We use only helpers that are joined to h by a random edge and lie outside X0+ . The reason is that base edges are always present: if a vertex w has a base edge to a high vertex h′ , then h′ marks this edge with probability θ ≥ 1/2, so w is a candidate with constant probability and may block its neighbors. A pair h′ w that is not a base edge, in contrast, is present and marked only with probability pθ = k/n. √ Lemma 4.9 (The base-low graph is well behaved). Assume M > 0 and zH < n/ B0 . Let E0 be the event that the following two properties hold: (a) every base-low vertex has at most 2λ random neighbors in L0 ; in particular, F0 has maximum degree at most B0 + 2λ = B; (b) X0+ ≤ n/4. Then E0 depends only on the random edges inside L0 , and, for all sufficiently large n, E0 fails with probability at most 2n−c−2 . Proof. Property (a). This is proved similarly to Lemma 4.6, counting only random edges inside L0 : by Fact 2.1(F1) and a union bound over at most n vertices, (a) fails with probability at most ne−λ/3 = n1−β/3 , which is at most n−c−2 since β = 2a ≥ 3(c + 3). A base-low vertex has at most B0 base neighbors, so if (a) holds, it has degree at most B0 + 2λ in F0 . Property (b). A vertex of X0+ lies in X0 , or is a base neighbor of a vertex of X0 , or is joined to a vertex of X0 by a random edge inside L0 . A vertex of the first two kinds is within distance two of H0 in G, so it lies in ZH ; there are at most zH of them. Let Y be the number of random edges inside L0 with at least one endpoint in X0 . Each vertex of the third kind is the endpoint outside X0 of such an edge, and distinct vertices of the third kind give distinct edges; so there are at most Y of them. Hence X0+ ≤ zH + Y. If Y ≤ 2λzH , then (b) holds. In this case, X0+ ≤ zH + 2λzH <

(1 + 2λ) n n √ ≤ . 4 B0

√ √ Here the second inequality uses zH < n/ B 0 . The last one is equivalent √to B 0 ≥ 4 + 8β ln n, √ √ which holds for all sufficiently large n depending only on c, since B 0 ≥ e ln n/2 / 2 grows faster than every multiple of ln n. Let us now calculate the probability that Y > 2λzH . The variable Y is a sum of independent indicators, one for each pair of vertices of L0 that has an end in X0 and is not a base edge, each equal to 1 with probability p. There are at most |X0 | · n such pairs, so E[Y ] ≤ |X0 | · n · 24

λ ≤ λzH , n

since X0 ⊆ ZH . By Fact 2.1(F1) with µ = λzH , we get P[Y > 2λzH ] ≤ e−λzH /3 . Since M > 0, there is a vertex h ∈ H0 with more than B0 neighbors in G, and h together with its neighbors lies inj Z√H , so λ ≥ 1, this gives e−λzH /3 ≤ e−B0 /3 . Moreover, k zH√≥ B0 + 1. Together with √ B0 = e ln n ≥ e ln n /2 for n ≥ 2. Since e ln n grows faster than every multiple of ln n, we have √

e ln n /6 ≥ (c + 2) ln n for all sufficiently large n depending only on c. Hence B0 /3 ≥ (c + 2) ln n, and P[Y > 2λzH ] ≤ e−B0 /3 ≤ n−c−2 . By the previous paragraph, (b) can fail only if Y > 2λzH , so (b) fails with probability at most n−c−2 . Conclusion. By a union bound over the failures of (a) and (b), E fails with probability at most −c−2 n + n−c−2 = 2n−c−2 . Both properties depend only on the random edges inside L0 , and hence so does E0 . The pool. Fix an outcome of F0 that satisfies E0 (mentioned in Lemma 4.9), and define the pool
U = L0 \ X0+ ∪ Q . The pool consists of the base-low vertices that we use as potential helpers: neither they nor their neighbors in F0 have base edges to H0 , and they have few neighbors in F0 . We exclude Q because a vertex with many base-low neighbors is easily blocked by a candidate neighbor. Every v ∈ U has at most t base neighbors in L0 , since v ∈ / Q, and at most 2λ random neighbors in L0 , since √ the fixed outcome of F0√satisfies Lemma 4.9(a). The pool is large, since |L0 | = n − M > n − n/ B 0 and |Q| ≤ zQ < n/ t. So (3)

degF0 (v) ≤ t + 2λ

(v ∈ U ),

n 2n n n , |U | ≥ n − √ − −√ ≥ 4 3 t B0

where the last inequality holds for all sufficiently large n, because B0 and t tend to infinity. The sample of a base-high vertex. Fix h ∈ H0 . The potential helpers of h are the base-low vertices joined to h by a random edge that h marks in Step 1; we call the set of these vertices the sample of h and denote it by Bh . To define it formally, give every pair {u, v} a coin κuv equal to 1 with probability θ, independently of each other and of all random edges. Step 1 marks a present edge uv with u ∈ Vhi and v ∈ Vlo exactly when κuv = 1; this has the same distribution as the algorithm, since every such edge uses its own coin. For v ∈ L0 \ X0 , the pair hv is not a base edge, by the definition of X0 . Let   Ihv = 1 hv ∈ R and κhv = 1 ,

Bh = {v ∈ L0 \ X0 : Ihv = 1} .

Then P[Ihv = 1] = pθ = k/n, and these indicators are independent over v. They depend only on the random edges and coins on pairs {h, v}, which are not inside L0 , so Bh is independent of F0 . If h ∈ Vhi , every vertex of Bh ∩ Vlo is a candidate. Lemma 4.10 (Many test vertices). Fix an outcome of F0 that satisfies E0 , and let h ∈ H0 . Then, for all sufficiently large n, with probability at least 1 − 2n−c−3 , at least ⌊k/3⌋ vertices of Bh ∩ U are isolated in F02 [Bh ]. Proof. Many sampled vertices in the pool. Let Yh = |Bh ∩ U | be the number of sampled vertices of h that lie in the pool. Since U ⊆ L0 \ X0 , the variable Yh is a sum of |U| independent indicators Ihv , 25

k each equal to 1 with probability k/n. Its mean is µ = |U| k/n ≥ 2k/3, by (3). Since 34 µ ≥ 34 · 2k 3 = 2, we have Yh < k/2 only if Yh ≤ 34 µ. By Fact 2.1(F2) with δ = 1/4, this has probability at most

e−µ/32 ≤ e−k/48 ≤ e−a ln n/48 = n−a/48 ≤ n−c−3 , using k ≥ a ln n and a ≥ 48(c + 3). Hence Yh ≥ k/2, except with probability at most n−c−3 . Few non-isolated sampled vertices. We apply Lemma 3.5 to the fixed graph F0 , with V0 = L0 \X0 and ∆ = B. The graph F0 has at most n vertices and, since the fixed outcome of F0 satisfies E0 , F0 has maximum degree at most B by Lemma 4.9(a). The sample Bh contains each √ vertex of V0 independently with probability k/n, and it is independent of F0 . Moreover, ln B ≤ ln n + 1 and k = O(ln n). So, by Lemma 3.5, fewer than q vertices of Bh are non-isolated in F02 [Bh ], except with probability n−q/2+o(1) . Since q ≥ 2c + 7, this is at most n−c−3 for all sufficiently large n. Conclusion. Suppose that Yh ≥ k/2 and that fewer than q vertices of Bh are non-isolated in F02 [Bh ]. Then, among the Yh vertices of Bh ∩ U, at least Yh − q ≥ k/2 − q are isolated in F02 [Bh ]. Since q is fixed and k ≥ a ln n, we have k/2 − q ≥ k/3 ≥ ⌊k/3⌋ for all sufficiently large n. By a union bound over the two failure events, this holds with probability at least 1 − 2n−c−3 . Test vertices. Let Th be the set of vertices of Bh ∩ U that are isolated in F02 [Bh ]; we call them the test vertices of h. On the event of Lemma 4.10, we have |Th | ≥ ⌊k/3⌋. The set Th is determined by F0 and Bh , and every v ∈ Th satisfies: (T1) degF0 (v) ≤ t + 2λ and NF0 [v] ∩ X0 = ∅, since v ∈ U; (T2) NF0 (v) ∩ Bh = ∅, since v is isolated in F02 [Bh ]; (T3) distinct u, v ∈ Th have distF0 (u, v) ≥ 3, so NF0 [u] ∩ NF0 [v] = ∅. If h is high, every test vertex v is a candidate, since h marks the random edge hv. So v joins S unless some neighbor of v is a candidate. By (T2), no neighbor of v is a candidate because of a mark from h. A neighbor of v can still be a candidate because of another base-high vertex h′ , in two ways: h′ itself may be a neighbor of v (through a random edge h′ v), or h′ may mark a random edge h′ w to a neighbor w of v. We do not know which base-high vertices are high, so we exclude both possibilities for all of H0 \ {h}. Robust success. Call v ∈ Th robustly successful if (S1) h′ v ∈ / R for every h′ ∈ H0 \ {h}, and (S2) Ih′ w = 0 for every w ∈ NF0 (v) and every h′ ∈ H0 \ {h}. By (T1), all pairs involved are non-edges of G. Figure 4 illustrates the test vertices and the two ways in which they can fail. The next lemma shows that robust success is enough: a robustly successful test vertex joins S and dominates h. Lemma 4.11 (Robust success implies domination). If E holds, h ∈ Vhi , and some v ∈ Th is robustly successful, then v ∈ S; hence h ∈ / A. Proof. Since E holds, we have v ∈ L0 ⊆ Vlo and Vhi ⊆ H0 (Lemma 4.6). Since v ∈ Bh , the edge hv is a random edge that h marks, so v is a candidate. It remains to show that no neighbor w of v is a candidate. The neighbor h is high, so it is not a candidate. Since v ∈ / X0 , no base edge joins v to H0 , and by (S1) no random edge joins v to H0 \ {h}; so every other neighbor w lies in L0 , that is, w ∈ NF0 (v). By (T1), w ∈ / X0 , so a mark on an edge h′ w with h′ ∈ Vhi ⊆ H0 would mean Ih′ w = 1. This is excluded by (T2) for h′ = h, and by (S2) for h′ ̸= h. So v is a candidate with no candidate neighbor, hence v ∈ S, and h ∈ NG [S]. 26

h′

h h′′

H0

v

x

v′ w

X0+ L0

not isolated in F02 [Bh ]

robustly successful: v∈S

(S2) fails: h′ w marked

(S1) fails: h′ v ′ ∈ R

Q

pool U = L0 \ (X0+ ∪ Q)

Figure 4: Case (2b), seen from a base-high vertex h. Grey vertices form the sample Bh : the baselow vertices outside X0 joined to h by a marked random edge (red, dashed). Sampled vertices in X0+ , such as the one next to the base edge h′′ x, or in Q are not used, and neither are the two sampled vertices within distance two of each other. The remaining sampled vertices are the test vertices Th ; their closed neighborhoods in F0 (dashed circles) are pairwise disjoint, so their outcomes are independent. A test vertex fails if another base-high vertex h′ has a random edge to it, violating (S1) (orange, dotted), or a marked edge to one of its neighbors w, violating (S2). A robustly successful test vertex v joins S and dominates h (Lemma 4.11). So it remains to show that, with high probability, some test vertex of h is robustly successful. Lemma 4.12 (Some test vertex succeeds). Fix an outcome of F0 that satisfies E0 , and an outcome of Bh for which the event of Lemma 4.10 holds. Then, for all sufficiently large n, the conditional probability that no vertex of Th is robustly successful is at most n−c−3 . Proof. We say that a test vertex fails if it is not robustly successful. The conditioning does not matter. Conditions (S1) and (S2) depend only on the random edges and coins on pairs between H0 \ {h} and L0 . The graph F0 and the sample Bh depend on other pairs, those inside L0 and those containing h. So, even after fixing F0 and Bh , each pair {h′ , v} with h′ ∈ H0 \ {h} and v ∈ L0 lies in R with probability p, and each Ih′ w with w ∈ L0 \ X0 equals 1 with probability k/n, all independently. One test vertex fails with probability at most 1/4. Fix v ∈ Th . Condition (S1) fails only if one of the at most M pairs {h′ , v} with h′ ∈ H0 \ {h} lies in R; each does so with probability p = λ/n. Condition (S2) fails only if one of the at most degF0 (v) · M indicators Ih′ w with w ∈ NF0 (v) and h′ ∈ H0 \ {h} equals 1; each does so with probability k/n. By a union bound and (T1), the probability that v fails is at most k M λ tM k 2λM k = + + . n n n n √ √ We bound the three terms. Since M < n/ B , the first is at most λ/ B 0 and the third is at most 0 √ √ 2λk/ B 0 . Since t ≤ n/(16M k), the second is at most 1/16. As λ and k are O(ln n) while B 0 grows faster than every power of ln n, the sum is at most 1/4 for all sufficiently large n. M p + (t + 2λ)M

27

Different test vertices are independent. The event that v fails is determined by the variables on the pairs {h′ , u} with h′ ∈ H0 \ {h} and u ∈ NF0 [v]. By (T3), these sets of pairs are disjoint for different test vertices, so the events are independent. Hence all test vertices fail with probability at most 4−|Th | . Conclusion. On the event of Lemma 4.10, we have |Th | ≥ ⌊k/3⌋ ≥ k/3 − 1. So the probability that all test vertices fail is at most 4−⌊k/3⌋ ≤ 4 · 4−k/3 = 4e−(ln 4)k/3 ≤ 4n−(ln 4)a/3 ≤ n−c−3 , using k ≥ a ln n, and (ln 4)a/3 ≥ c + 4 for a ≥ 48(c + 3), and n ≥ 4. √ √ Lemma 4.13 (Case (2b)). If M > 0, zH < n/ B 0 and zQ < n/ t, then, for all sufficiently large n, A = ∅ with probability at least 1 − n−c−1 . Proof. Bad base-high vertices. Call h ∈ H0 bad if the event of Lemma 4.10 fails, or no vertex of Th is robustly successful. Fix an outcome of F0 that satisfies E0 , and fix h ∈ H0 . Conditional on this outcome, the event of Lemma 4.10 fails with probability at most 2n−c−3 , by that lemma. For every outcome of Bh for which this event holds, Lemma 4.12 shows that, conditional on F0 and Bh , no vertex of Th is robustly successful with probability at most n−c−3 . Hence, conditional on F0 , the vertex h is bad with probability at most 2n−c−3 + n−c−3 = 3n−c−3 . We need no independence between different base-high vertices: a union bound over the at most n vertices of H0 shows that, conditional on F0 , some vertex of H0 is bad with probability at most 3n−c−2 . Since this holds for every outcome of F0 that satisfies E0 , the probability that E0 holds and some vertex of H0 is bad is at most 3n−c−2 . No active vertex. Suppose that E and E0 hold and no vertex of H0 is bad. Let h ∈ Vhi . Then h ∈ H0 by Lemma 4.6, and since h is not bad, some v ∈ Th is robustly successful. By Lemma 4.11, h∈ / A. Since A ⊆ Vhi , we get A = ∅. The failure probability. By the previous paragraph, A ̸= ∅ only if E fails, E0 fails, or E0 holds and some vertex of H0 is bad. By Lemma 4.6, E fails with probability at most n1−β/3 ≤ n−c−2 , since β = 2a ≥ 3(c + 3). By Lemma 4.9, E0 fails with probability at most 2n−c−2 . By the first paragraph, the event E0 holds and some vertex of H0 is bad with probability at most 3n−c−2 . By a union bound, A ̸= ∅ with probability at most n−c−2 + 2n−c−2 + 3n−c−2 = 6n−c−2 ≤ n−c−1 , for n ≥ 6. We are now ready to prove Lemma 4.5. Let us restate it here for convenience. Lemma 4.5. For every base graph G and all sufficiently large n, condition (1) holds with probability at least 1 − n−c−1 . Proof of Lemma 4.5. The quantities M , zH and zQ depend only on G, so for a given G exactly one of the following applies: M = 0, Case (1), Case (2a), or Case (2b). If M = 0, then H0 = ∅. Let E be the event of Lemma 4.6. If E holds, then A ⊆ H0 = ∅ by that lemma, so condition (1) holds. Hence it fails with probability at most P[E c ] ≤ n1−β/3 ≤ n−c−1 , since β = 2a ≥ 3(c + 3). In Cases (1) and (2a), Lemmas 4.7 and 4.8 show that condition (1) holds with probability at least 1 − n−c−1 . In Case (2b), Lemma 4.13 shows that A = ∅, and hence that condition (1) holds, with probability at least 1 − n−c−1 . 28

4.2.2

Proof of Theorem 4.1 √ We can now show the desired O( log n) round complexity for solving MIS in the smoothed setting. Let us restate Theorem 4.1 here for convenience. Theorem 4.1. For every constant c > 0, there is a constant β ≥ 1, depending only on c, such that the following holds for all sufficiently large n. Let G be any graph on n vertices, and let G be its smoothing with λ = β ln n. There is a randomized LOCAL algorithm √ that, given G, the number n, and distinct identifiers of O(log n) bits, computes an MIS of G in O( log n) rounds with probability at least 1 − n−c . The probability is over the random edges and the random bits of the algorithm. Proof. Recall that the algorithm outputs I = S ∪ J ∪ K, where S is the set of helpers of Step 1, J is the set computed in Step 2, and K is the output of the algorithm of Proposition 2.3 on G[Vrest ] in Step 3. We say that Step 3 succeeds if K is an MIS of G[Vrest ]. We show that I is an MIS of G whenever condition (1) holds and Step√3 succeeds, that both happen with probability at least 1 − n−c , and that the algorithm takes O( ln n) rounds. Independence. The sets S and J are independent in G: a vertex joins S only if it is a candidate with no candidate neighbor, so no two vertices of S are adjacent, and J is independent by Lemma 4.4. If Step 3 succeeds, then K is independent as well. Moreover, no edge joins any two of the three sets: J ⊆ A = Vhi \ NG [S] has no neighbor in S, and K ⊆ Vrest = Vlo \ NG [S ∪ J] has no neighbor in S ∪ J. Hence, if Step 3 succeeds, I is independent in G. Maximality. Assume that condition (1) holds and Step 3 succeeds, and let v ∈ / NG [S ∪ J]. If v were high, it would be active, since v ∈ / NG [S]; but Lemma 4.4 gives A ⊆ NG [J], a contradiction. So v is low, and hence v ∈ Vrest . Since K is an MIS of G[Vrest ], we get v ∈ NG [K]. Hence every vertex lies in NG [I]. Condition (1) holds and Step 3 succeeds with probability at least 1 − n−c . By Lemma 4.5, condition (1) fails with probability at most n−c−1 , for every base graph G and all sufficiently large n. Next, every low vertex has degree at most B in G, so G[Vrest ] has at most n vertices and maximum degree at most B. Step 3 runs the algorithm of Proposition 2.3 with ∆ = B, using fresh random bits, so for every outcome of the earlier steps it fails with probability at most n−c−1 . By a union bound, condition (1) holds and Step 3 succeeds with probability at least 1 − 2n−c−1 ≥ 1 − n−c . Running time. The set-up takes one round. Step 1 takes O(1) rounds, since the marks, the candidate status and the membership in S are each sent to the neighbors in one round. √ One more round tells every vertex whether it is active, and Gather then takes ℓ + 1 = O( ln n) rounds by Lemma 2.4. One more round tells every vertex √ whether it has a neighbor in√S ∪ J, and hence whether it lies in Vrest . Finally, B =√B0 + 2λ ≤ 2e ln n for large n, so log B = O( ln n), and Step 3 3 e takes O(log B) + O(log log n) = O( ln n) rounds by Proposition 2.3. Each step runs for a number √ of rounds that depends only on n and β, so the total is O( ln n).

4.3

Extension to the Symmetric Difference Model

Theorem 4.1 also holds for the symmetric-difference model Gs = G△G(n, p) of Section 1.5, with the same algorithm. Let p ≤ 1/2, and let G′ ⊆ G keep each edge of G independently with probability γ = (1 − 2p)/(1 − p). Let G ′ be the smoothing of G′ , that is, G′ together with each non-edge of G′ added independently with probability p. A non-edge of G is present in G ′ with probability p, and an edge of G is present with probability γ + (1 − γ)p = γ(1 − p) + p = 1 − p, independently over all pairs; so G ′ has the same distribution as G△G(n, p). Theorem 4.1 holds for every base graph, in particular for every outcome of G′ , and the algorithm does√not use the base graph. Averaging over G′ , the algorithm computes an MIS of G△G(n, p) in O( log n) rounds with probability at least 1 − n−c . 29

Theorem 4.14. For every constant c > 0, there is a constant β ≥ 1, depending only on c, such that the following holds for all sufficiently large n. Let G be any graph on n vertices, and let Gs = G△G(n, p) be the smoothed graph with p = β ln n/n. There is a randomized LOCAL algorithm that, of O(log n) bits, computes an MIS of Gs in √ given Gs , the number n, and distinct identifiers −c O( log n) rounds with probability at least 1 − n . The probability is over the random edges and the algorithm’s random bits.

5

Lower Bound: Less Smoothing Gives No Advantage

The algorithm we provide in Section 4 shows that when one smooths with parameter √ p ≥ β ln n/n for a sufficiently large constant β, MIS can be solved on the resulting graph in O( log n) rounds with high probability. In this section, we show that this smoothing parameter choice is tight (up to a constant factor), i.e., when the smoothing parameter is ≤ (1/2 − δ) ln n/n, for any constant δ ∈ (0, 1/2], any algorithm that solves MIS on the smoothed graph takes asymptotically more time. More concretely, we show the following theorem. Theorem 5.1. Fix constants δ ∈ (0, 1/2] and σ ∈ (0, 1], and let p = p(n) satisfy p ∈ [0, (1/2 − δ) ln n/n]. Any randomized LOCAL algorithm that, for every  graph  G of n nodes computes an MIS log n of G = G ∪ G(n, p), with probability at least σ, requires Ω log log n rounds. The probability is over the smoothing and the algorithm’s private randomness. This bound holds even when nodes know the values of n, p, use IDs exactly in [n], and can distinguish between edges of G and edges added by the smoothing. At a high level, we show a reduction from the problem of (non-smoothed) MIS to the problem of MIS on a smoothed graph for smoothing parameter p ≤ (1/2 − δ) ln n/n, for any constant δ ∈ (0, 1/2]. More concretely, we show how to reduce the problem of solving an MIS on a graph H with h nodes to the problem of solving MIS on a smoothed graph G with n nodes. Thus, any algorithm A that solves MIS on smoothed graphs in time T can be simulated by nodes in the original instance in Tsim rounds, resulting in any instance of MIS being solved in Tsim . By carefully developing a reduction from any graph H to a smoothed instance G, we ensure that Tsim = T +O(1). Note that G is not the smoothing of H but of a graph constructed from H. This reduction, as we show, holds for any MIS algorithm whose running time satisfies T < ε ln n/ ln ln n (see Lemma 5.7), where ε is a constant given in Section 5.2. Since the size of the original graph h is polynomially related to the size of the smoothed graph n (i.e., ln h/ ln ln h = Θ(ln n/ ln ln n)), this condition on the reduction amounts to T = O(ln h/ ln ln h). As a result, when combined with the recent result of Khoury and Schild [22] that shows that any randomized algorithm that takes o(ln h/ ln ln h) rounds to solve (non-smoothed) MIS does so with only subconstant probability on some graphs, we see that any algorithm that solves MIS on smoothed graphs with probability at least a constant σ must take Ω(ln n/ ln ln n) rounds. We now give a proof sketch of Theorem 5.1 in Section 5.1; Section 5.2 proves the reduction, and Section 5.3 applies the external lower bound. In Section 5.4, we show how to extend this proof to the smoothing model where both edge insertions and deletions take place.

5.1

Proof Sketch of Theorem 5.1

In Section 5.2, we show how to reduce the problem of MIS on a graph H to an instance of MIS on a constructed graph G by (i) replacing each node u in H with an appropriately large clique Cu , (ii) for every edge (u, v) ∈ E(H), forming complete bipartite graphs between the two cliques Cu 30

and Cv (i.e., each node of Cu is connected to each node of Cv ), and (iii) adding several “padding” nodes to G that are just isolated nodes that will serve a purpose after smoothing. Once G is constructed, we apply smoothing to it to obtain the smoothed graph G = G ∪ G(n, p). We then show that, whenever every replacement clique in G contains a protected node, any solution to MIS on G, I, maps to a solution to MIS on the input graph H, J, using the following mapping rule J = {u ∈ H : I ∩ Cu ̸= ∅}.11 This is shown by showing that the existence of protected nodes in each clique in G ensures that J is an MIS of H after applying the mapping rule. Consider a node a ∈ Cu in G (i.e., a is a node in the clique of nodes in G representing node u in H), and let NG (a) and NG (a) represent a’s neighborhoods in G and G respectively. Node a is a protected node in G if NG (a) = NG (a). For J to be an MIS of H, both independence and maximality conditions must hold. Independence follows from the edges between cliques corresponding to adjacent nodes of H. To establish maximality, suppose that neither u nor any neighbor of u belongs to J. The protected node in Cu would then neither belong to I nor have a neighbor in I, contradicting maximality of I. We show in Lemma 5.2 that with probability 1 − o(1) every replacement clique contains a protected node. Then, as we show in Lemma 5.3, any solution to MIS on G, I, can be projected to a solution on H, J, where the mapping is defined as above. The previous paragraph discussed how to map an MIS on a (virtual) G to an MIS on H. The other main component of the reduction is that if we have a fast MIS algorithm A, by simulating it on G, we can quickly obtain the MIS on H. In other words, we need to show that the time taken by nodes in H to simulate A on G is not too much. Suppose that node u ∈ H simulates some node w ∈ G and w’s neighbor in G is simulated by node v ∈ H. To simulate a round of A on G, u must transmit to and receive information from every such node v. We want to show that one round of the simulation on G corresponds to one round of actual computation on H with probability 1−o(1). This is shown in steps. Recall that a node u ∈ H simulates its clique of nodes Cu in G. We want to show that the adjacency induced by the clique nodes of graph G (which captures the adjacency of the original graph H) is preserved in G with probability 1 − o(1). We show in Lemma 5.4 that for all pairs of nodes a ∈ Cu , b ∈ Cv such that u ̸= v and Cu , Cv are two cliques in G, then if (u, v) ∈ / E(H), it is the case that (a, b) ∈ / E(G) with probability 1 − o(1). However, this is not enough to ensure a fast simulation, where one simulated round takes one actual round, as paths through padding nodes must also be accounted for. For an illustrative example, suppose u and v locally simulate the nodes in their respective shaded boxes in Figure 5. Relaying a message across the edge (q3 , q4 ) then requires communication between u and v which are two hops apart in H. We show that, with probability 1 − o(1), paths through padding nodes do not provide additional communication routes between any such Cu and Cv within the T rounds being simulated. More formally, let F be the graph obtained from G by removing all inter-clique edges and all intra-clique edges. For each u ∈ H and a ∈ Cu , take the T + 2 hop ball centered around a induced in F . We subsequently construct a virtual forest F where the root of each tree corresponds to a node a ∈ Cu , for all u ∈ H and the depth of each tree is at most T + 2. Lemmas 5.5 and 5.6, taken together, show that there is a coupling under which, with probability 1 − o(1), every virtual tree in F is identical, including node IDs, to its corresponding radius-(T + 2) neighborhood in F . By combining Lemmas 5.4, 5.5, and 5.6, we see that with probability 1 − o(1), each node u ∈ H can simulate its clique Cu and the attached virtual trees using one actual round for each round of the simulation. More generally, we show in Lemma 5.7 that the simulation of MIS on G by nodes in the original graph H and projection of the solution on G back to the original graph H takes 11

Here, we use the term replacement clique to emphasize that these are cliques in G formed as a result of replacing nodes in H with a clique in G, and explicitly exclude cliques that may form in G as a result of smoothing.

31

Real communication graph H (2 hops) u

u a ∈ Cu

q1

w

v

Padding route in G (7 hops)

q2

q3

q4

q5

v q6

b ∈ Cv

Figure 5: An illustrative assignment of virtual nodes to u and v. Nodes u and v are distance 2 apart in the original graph H. However, simulation of a message sent over virtual edge (q3 , q4 ) requires communication over the two-hop path between u and v in H. ε ln n T + O(1) rounds, for T < ln ln n , where ε is a constant that satisfies certain conditions seen in the analysis. Finally, we complete the lower bound proof in Section 5.3 by leveraging the lower bound graph of Khoury and Schild [22]. We apply our reduction to that lower bound graph, which takes on the role of input graph H. If any algorithm A existed that allowed us to solve MIS on a smoothed graph in T = o(ln n/ ln ln n) time with constant probability, the nodes of the original graph H could simulate its execution on the virtual graph G in T + O(1) rounds. The resulting MIS output on G could then be locally mapped to an MIS on the original graph H (without expending additional rounds). This would solve MIS on H in o(ln n/ ln ln n) = o(ln h/ ln ln h) rounds, which would contradict the lower bound of [22].

5.2

Reduction from MIS to MIS on Smoothed Graphs

This section proceeds as follows. We first state the various parameter choices and introduce all relevant constants used throughout the section. Subsequently, we formally describe the construction of the smoothed graph G from the input graph H. We then explain how to map the output MIS of the simulation on G to an MIS for the input graph H. Finally, we bound the time taken by nodes in H to perform the simulation. Parameter choices. Throughout the rest of this proof, we use the following notation and parameter choices. Fix constants δ ∈ (0, 1/2] and σ ∈ (0, 1]. Choose a fixed integer d > 1/δ and constants α, ε satisfying a0 := 12 − δ + d1 < α < 21 and 0 < ε < α − a0 . For sufficiently large n, set h = ⌊n1/d ⌋, k = ⌈20enp ln h⌉, r = hk, and s = ⌊nα ⌋. Since enp ≤ n1/2−δ , we have
r = hk ≤ n1/d 20n1/2−δ ln n + 1 ≤ na0 +o(1) . Consequently, r ≤ s < n for sufficiently large n. Moreover, ps2 = O(n2α−1 ln n) = o(1). Constructing G from input graph H. The original graph is H and our goal is to construct a virtual graph G, apply smoothing to it to obtain G and subsequently simulate an MIS algorithm A on G. This is visually represented in Figure 6. 32

Graph construction Replace nodes with cliques. For each edge of H, connect the cliques with a complete bipartite graph. Add isolated padding nodes.

Independently add each missing edge with probability p.

Original graph H

Constructed graph G

h nodes

n nodes

Smoothed graph G n nodes

G = G ∪ G(n, p)

Computation performed on H 1

Local setup

Generate each clique Cu and its attached virtual trees.

2

Simulation

Simulate A on G to obtain clique-node outputs.

T rounds

3

Projection

Select u in H iff some node in Cu is selected.

0 rounds

O(1) rounds

Total: T + O(1) real rounds

Figure 6: Construction and simulation in the reduction. The input graph H is expanded to G and smoothed to G. The nodes of H simulate A on G in T + O(1) rounds and project its clique-node outputs back to an MIS of H. Now, we describe the construction of G from H. For each node u ∈ H, replace it with a clique S (1) (k) of k nodes Cu = {cu , . . . , cu }. Let C = u∈H Cu , and let r = |C|. In total, there are r = hk clique nodes in G, which are interconnected as follows: for each edge (u, v) ∈ E(H), add edges between all nodes in Cu and Cv such that the edges form a complete bipartite graph between the cliques. Finally, we add n − r padding nodes q1 , q2 , . . ., qn−r to G, which are just isolated nodes (i.e., with no neighbors in G). An example of this construction is shown in Figure 7. Finally, we discuss nodes’ IDs. For the nodes in H, we assume that their IDs are unique and in the range [h]. (i) We assign unique IDs, in the range [n], to nodes in G as follows: assign some clique node cu the ID (idH (u) − 1)k + i, and assign some padding node qj the ID r + j. Developing a mapping from MIS on G to MIS on H. We now show how to take a potential solution to the MIS on G and project it to the nodes in the input graph H. In particular, we show that if an MIS I is calculated on G, that will translate to an MIS J = {u ∈ H : I ∩ Cu ̸= ∅} on H with probability 1 − o(1) by leveraging the existence of protected nodes. Recall that a protected node a ∈ G is defined such that its neighborhood in G is the same as its neighborhood in G, i.e., NG (a) = NG (a). The existence of such a node in each clique allows us to show that the maximality of the MIS is conserved. We show that each clique contains such a protected node with probability 1 − o(1) in Lemma 5.2. Subsequently, we show that, when every replacement clique has such a protected node, the way J is defined results in a valid MIS on H in Lemma 5.3. Lemma 5.2. With probability at least 1 − h−9 , every replacement clique contains a protected node. Proof. A clique node has at most n potential edges (edges not in G) to padding and other clique nodes. The probability of a node being a protected node (not having any such edges added during smoothing) is at least 33

Original graph H: h = 3 nodes u

v

w Replace each node by a clique of size k = 4. An edge in H is replaced by a complete bipartite graph between corresponding cliques in G.

Constructed graph G: n = 12 + 1,200 = 1,212 nodes Cu

Cv

Cw

c(1) u

c(2) u

c(1) v

c(2) v

c(1) w

c(2) w

c(4) u

c(3) u

c(4) v

c(3) v

c(4) w

c(3) w

Complete bipartite graph K4,4 between Cu and Cv (16 edges)

q1

q2

···

q1199

q1200

1,200 isolated padding nodes (>> hk).

Figure 7: An example of how the original graph H of h nodes is converted into the graph G with n nodes. For visual clarity, we choose values of k and n for illustrative purposes rather than correct values. Here, h = 3, k = 4, and the number of padding nodes is 1200, which captures the idea that the number is significantly larger than hk.

34

(1 − p)n = exp(n ln(1 − p)) = exp(−np − O(np2 )) Taylor expansion of ln(1 − p); p ≤ 1/2 for sufficiently large n since np2 = O((ln n)2 /n) = o(1)

= exp(−np − o(1)) ≥ 21 e−np

for sufficiently large n. For distinct nodes in the same clique, the potential edge sets are disjoint: their only possible shared edge joins those two nodes and is already an existing intra-clique edge. Thus their protection events are independent, even though they may share potential outside neighbors. Consequently, Pr[Cu has no protected node] ≤ (1 − 21 e−np )k ≤ exp(−ke−np /2) ≤ h−10 . A union bound over the h cliques results in the claim. Lemma 5.3. If every replacement clique contains a protected node, then every MIS I of G projects to an MIS of H via J = {u ∈ H : I ∩ Cu ̸= ∅}. Proof. In any MIS I on G, there is at most one selected node in each clique. If (u, v) ∈ E(H), then the complete bipartite graph between Cu and Cv prevents the two cliques from both containing a selected node. Thus the MIS J on H is independent. To show the maximality of J, suppose that some node u and all its neighbors in H are not in J. This implies that all clique nodes representing u and its neighbors in H are also not in I. We show that this leads to a contradiction with the assumption that I represents an MIS. Consider a (i) protected node cu in G. It must not be in I. Its neighborhood consists of nodes in Cu and nodes in the cliques representing neighbors of u in H. As mentioned earlier, none of these nodes are in (i) the MIS I. The protected node cu has no added neighbor outside Cu . Hence it has no neighbor in I, contradicting the maximality of I. Therefore, every node not in J has a neighbor in J. As a result, J is an MIS of H. Simulation time preservation. We now show that nodes on the input graph H will take T + O(1) rounds to simulate algorithm A on G. We do this by first showing that from G to G, no additional inter-clique edges are added with probability 1 − o(1) in Lemma 5.4. Conditioning on this event, we subsequently show that each node u in H can locally simulate the radius-(T + 2) neighborhoods rooted at the nodes of Cu , after removing all inter-clique and intra-clique edges. This is done by first upper bounding the number of such nodes that need to be simulated in Lemma 5.5 and subsequently showing that such subgraphs are disjoint with probability 1 − o(1) for every pair of nodes u, v ∈ H in Lemma 5.6. Lemma 5.4. G contains an edge not present in G between two clique nodes with probability at most o(1).
Proof. Recall that there are r = hk clique nodes in G. There are at most 2r ≤ r2 possible edges between clique nodes in G that can be added during smoothing to get G. Each edge is added with probability p during smoothing. A union bound gives that an edge not present in G between two cliques is contained in G with probability at most pr2 . Since p = O(ln n/n) and r ≤ na0 +o(1) (and recall that a0 < 1/2), we have pr2 ≤ n2a0 −1+o(1) = o(1). The smoothing of G to G is a random process. We focus on the radius T + 2 neighborhoods of clique nodes in F , defined below, and show a coupling between the smoothing used to generate this graph and a random process to construct a virtual forest F of trees of depth at most T + 2, where 35

G

Cu

F [P2 (a)]

F Cv

ℓ=2 a q1

a

b q2

q5

q1

q3

q3

q4

q4

a

b q2

q5

q1

q2

q3

Figure 8: An example of how F [P2 (a)] is generated from graph G. Both inter-clique edges (green) and intra-clique edges (red) are removed from G when creating F . each tree is rooted at a clique node a ∈ C. We show that the two constructions can be coupled, while preserving the correct distribution of each construction, so that, with probability 1 − o(1), all virtual trees in F with root nodes a ∈ C match the corresponding neighborhoods F [PT +2 (a)], including nodes IDs. Together with Lemma 5.4, this allows each node u ∈ H to simulate A on its clique Cu and its attached virtual trees locally, while simulating communication between adjacent cliques over the corresponding edges of H. 
 We first define F [PT +2 (a)] formally. Define a graph F = V (G), E(G) \ C2 . Observe that all inter-clique and intra-clique edges of G are removed. For each clique node a ∈ C, define PT +2 (a) = {z : distF (a, z) ≤ T + 2}, where distF (a, z) represents the shortest distance between nodes a and z in F . Then, F [PT +2 (a)] is the subgraph of F induced by PT +2 (a). Lemmas 5.5 and 5.6 imply that, with probability 1 − o(1), all the neighborhoods F [PT +2 (a)], for all a ∈ C, simultaneously are identical to their corresponding virtual trees, and hence are trees. See Figure 8 for an example illustration of one such F [PT +2 (a)]. We now describe the construction of the virtual forest F. At each of the r = hk clique nodes, generate a virtual tree to depth T + 2 as follows. Start with a given clique node as the root at level 0 and recursively perform the following process. Independently for each node at level < T + 2, draw the number of children of the node, W , from a binomial distribution Bin(n − r, p). Notice that E[W ] = (n − r)p. Choose W distinct IDs for these children uniformly at random from [r + 1, n]. Note that this may result in the same ID appearing multiple times in a given tree or in multiple trees. We show that this happens with probability o(1) by Lemma 5.5 and Lemma 5.6. Recall that s = ⌊nα ⌋. Subsequently, we use X to denote the total number of nodes in the virtual forest F . Lemma 5.5. If T < ε ln n/ ln ln n, then Pr[X > s] = o(1). Proof. Each node generated below level T + 2 independently has expected (n − r)p children. By induction, the expected number of nodes at level j, across all r trees is r((n − r)p)j . Summing up 36

over all levels gives E[X] ≤ r(T + 3) max{1, np}T +2 . Recall that the first term r ≤ na0 +o(1) . Notice that for sufficiently large n, max{1, np} ≤ ln n, and also notice that T + 2 < ε ln n/ ln ln n + 2. From this we see that the second term T + 3 = no(1) . Finally, we can bound the third term too: max{1, np}T +2 ≤ (ln n)ε ln n/ ln ln n+2 ≤ nε+o(1) . Thus we get E[X] ≤ na0 +ε+o(1) . Applying Markov’s inequality gives us Pr[X > s] ≤ E[X]/s = o(1) because a0 + ε < α. Lemma 5.6. For r ≤ s = o(n), there is a coupling of the construction of the virtual forest F with a smoothing leading to G such that, with probability at least 1 − Pr[X > s] − O(ps2 ), the following is true for all a ∈ C: the virtual tree rooted at a is identical to F [PT +2 (a)], including node IDs. These neighborhoods are pairwise disjoint, and no edge of F joins two different neighborhoods. In particular, all nodes in the virtual forest have distinct IDs. Proof. We use the following equivalent description of the preceding virtual forest construction: at each node i at a level < T + 2, independently for each padding ID j ∈ [r + 1, n], create a child of i with ID j with probability p. We use deferred decisions to couple the virtual forest construction with the smoothing process and bound the probability of any disagreement between a virtual tree and its corresponding neighborhood in F . Generate F and reveal F together, exploring in breadthfirst order from all r clique nodes. Initially, the set of discovered nodes consists of all r clique roots. The goal is to discover all nodes of the virtual forest and, without failure, verify that F contains no edges between different trees and no edges within a tree other than its parent-child edges. We stop the comparison and declare failure if either (i) a mismatch occurs, as specified below, or (ii) adding another virtual node would make the total number of virtual nodes, including the roots, exceed s. When expanding a node at a level < T + 2, consider each padding node ID in turn and perform a Bernoulli trial with probability p. If the ID is undiscovered at the start of the trial (i.e., has not been assigned to a node in F before), use the same coin to decide whether it becomes a virtual child and whether the corresponding edge is present in F . (It was not previously decided if this edge was in F or not.) If the coin selects this ID, create the corresponding virtual child, mark its ID as discovered, and add the corresponding edge to F . If the ID was already discovered at the start of the trial, then it is considered a mismatch if the trial selects it. Before the size cutoff, at most s nodes are expanded, and at most s padding IDs have been discovered. At each trial involving an already discovered ID, conditional on everything revealed so far, the probability of the ID being chosen is p. Taking a union bound over the at most s2 such trials, we see that the probability of a mismatch in the form of an ID repetition before the cutoff is ≤ ps2 . If the exploration finishes without declaring a failure, i.e., X ≤ s and no mismatch as described above occurs, we proceed with the checks on inter-tree and intra-tree edges. In particular, for every undecided edge in F between a pair of distinct discovered nodes having at least one padding endpoint, flip a coin with probability p to determine whether the edge exists.12 If any such edge exists, it is considered a mismatch. These checks include pairs within a tree, between different trees, and between nodes at level T + 2. There are at most s2 such pairs to check. Taking a union bound over all such pairs, the probability of a mismatch is ≤ ps2 . Every virtual coin is fresh, and every shared coin reveals a previously unexposed edge of F . After any stop, complete the virtual construction according to its original sampling rule and complete all remaining smoothing trials independently. This includes trials between clique nodes, whose edges do not enter F . Thus both constructions retain their correct distributions. 12

We mention that at least one endpoint is a padding node to avoid checks between two clique nodes.

37

If X ≤ s and neither type of mismatch occurs, all virtual IDs are distinct and the explored edges are exactly the tree edges. Consequently, the virtual trees agree simultaneously with F [PT +2 (a)] for every a ∈ C. These neighborhoods are pairwise disjoint, with no edges of F between them. Edges from level-(T + 2) nodes to undiscovered padding nodes are allowed, since they lead outside the specified radius. The probability that any claimed property fails is therefore at most Pr[X > s] + 2ps2 , which proves the lemma. Lemma 5.7. Let A be a randomized LOCAL algorithm that, for every n node base graph G, computes an MIS of G = G ∪ G(n, p) with probability at least σ, over the smoothing and its private randomness, using at most T < ε ln n/ ln ln n rounds. The nodes of H can simulate T rounds of the virtual execution on G and project the solution back to the original graph H in T + O(1) rounds. The projected solution is an MIS of H with probability at least σ − o(1). Proof. There are two things to argue here. First, that a solution of MIS on G can be mapped to a valid solution of MIS on H. By Lemmas 5.4, 5.5, and 5.6, the virtual trees and the edges between clique nodes are identical to those of a genuine G with probability 1 − o(1). The depth T + 2 ensures that omitted neighbors of boundary padding nodes cannot affect clique nodes’ outputs within T rounds. Thus, with probability 1−o(1), the local simulation reproduces the clique nodes’ outputs of a genuine execution of A on G. Algorithm A, when executed on G, outputs an MIS with probability at least σ. By Lemmas 5.2 and 5.3, we see that the solution on an MIS for G can be mapped to an MIS on H with probability 1 − o(1). A union bound over the failure of the simulation, the failure of A, and the failure of protection gives overall success probability at least σ − o(1) − h−9 = σ − o(1). Second, we need to argue that the total time to simulate A on G by nodes in H is T + O(1) rounds. Each node u ∈ H locally generates and simulates its clique Cu and the attached virtual trees. After O(1) rounds of initialization, communication within a clique and its trees is simulated locally. For every (u, v) ∈ E(H), all messages between Cu and Cv are combined into one message over (u, v). Since LOCAL messages have unbounded size, one virtual round takes one real round. Thus the simulation takes T + O(1) rounds. Furthermore, the mapping of the MIS obtained for G to one for H can be computed by all nodes in H locally. Thus the total time for the simulation is T + O(1) rounds.

5.3

Obtaining the Ω(ln n/ ln ln n) Lower Bound

In this section, we prove that Theorem 5.1 holds true. We now combine Lemma 5.7 with the lower bound of Khoury and Schild [22]. Their result implies that there exists a constant cKS > 0, depending on σ, such that, for all sufficiently large h, any randomized LOCAL algorithm that computes an MIS with probability at least σ/2 on every graph of h nodes requires at least cKS lnlnlnhh rounds. This holds even when the nodes have IDs exactly in [h] and know h. Proof of Theorem 5.1. Fix δ, σ, and p = p(n)as in the theorem. Use the parameters chosen in KS Section 5.2, and choose a constant η ∈ (0, min ε, c2d ). Suppose that, for some sufficiently large n, an algorithm A satisfying the theorem’s success guarantee has round complexity T < η lnlnlnnn . Recall that h = ⌊n1/d ⌋. Since η < ε, Lemma 5.7 applies: for every input graph H of h nodes, its nodes can simulate A on the constructed smoothed graph and project the outputs to an MIS of H in T + O(1) rounds, with probability at least σ − o(1). For sufficiently large n, this probability is at least σ/2. The construction parameters are fixed independently of H, so this gives one randomized LOCAL algorithm that succeeds on every graph of h nodes. 38

Since d is fixed and h = ⌊n1/d ⌋, ln h = ln ln h



1 + o(1) d



ln n . ln ln n

Our choice of η therefore gives, for sufficiently large n, T + O(1) <

cKS ln n ln h < cKS . 2d ln ln n ln ln h

Thus the derived algorithm solves MIS on every graph of h nodes with probability at least σ/2 in fewer rounds than permitted by the Khoury–Schild lower bound, which is a contradiction. Consequently, any algorithm satisfying the theorem’s success guarantee requires at least η ln n/ ln ln n rounds for sufficiently large n. Since η is a positive constant, this proves the claimed Ω(ln n/ ln ln n) lower bound. The construction assigns IDs exactly in [n], and the simulation can provide the values of n and p and distinguish edges of G from edges added by smoothing. Hence the argument also establishes the final assertion of the theorem.

5.4

Allowing Both Edge Additions and Deletions during Smoothing

The same lower bound holds when smoothing independently adds each missing edge with probability p and deletes each existing edge with probability p. That is, Gs = G△G(n, p) instead of G = G ∪ G(n, p). Theorem 5.8. Fix constants δ ∈ (0, 1/2] and σ ∈ (0, 1], and let p = p(n) satisfy p ∈ [0, (1/2 − δ) ln n/n]. Any randomized LOCAL algorithm that, for every  graph  G of n nodes computes an MIS log n of Gs = G△G(n, p), with probability at least σ, requires Ω log log n rounds. The probability is over the smoothing and the algorithm’s private randomness. This bound holds even when nodes know the values of n, p, use IDs exactly in [n], and can distinguish between surviving edges of G and edges added by the smoothing. Proof. Use the same construction and parameter choices as in Section 5.2. Since the padding nodes are isolated
in G, every edge of G has both endpoints among the r clique nodes. Consequently, |E(G)| ≤ 2r . A union bound therefore gives   r Pr[some edge of G is deleted] ≤ p|E(G)| ≤ p ≤ n2a0 −1+o(1) = o(1), 2 where we use p = O(ln n/n), r ≤ na0 +o(1) , and a0 < 1/2. Thus, an algorithm that succeeds with probability at least σ under additions and deletions succeeds with probability at least σ − o(1) on the addition-only instances produced by our construction. The simulation and projection argument in Section 5.2 therefore still gives an algorithm on H taking T + O(1) rounds and succeeding with probability at least σ − o(1). The argument in Section 5.3 then establishes the claimed lower bound.

AI Disclosure We investigated the potential of applying smoothed analysis to distributed MIS, and in particular, √ the possibility of obtaining an O( log n)-round MIS algorithm via smoothing, in March 2026. 39

This was inspired by the work that uses smoothed analysis for graph isomorphism, that appeared in STOC 2025 [3]. More recently, we then asked ChatGPT (GPT-6.1 Sol Ultra) to explore this possibility, and it produced most of the technical results presented in this paper. We significantly reworked the proofs and exposition to make them understandable to humans. The authors take full responsibility for all the results.

References [1] Elad Aigner-Horev, Dan Hefetz, and Michael Krivelevich. Minors, connectivity, and diameter in randomly perturbed sparse graphs. Eur. J. Comb., 127:104152, 2025. URL: https://doi. org/10.1016/j.ejc.2025.104152, doi:10.1016/J.EJC.2025.104152. [2] Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567–583, 1986. [3] Michael Anastos, Matthew Kwan, and Benjamin Moore. Smoothed analysis for graph isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2098–2106, 2025. [4] László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684– 697. ACM, 2016. doi:10.1145/2897518.2897542. [5] László Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1237–1246. ACM, 2019. doi:10.1145/3313276.3316356. [6] László Babai, Paul Erdős, and Stanley M. Selkow. Random graph isomorphism. SIAM J. Comput., 9(3):628–635, 1980. doi:10.1137/0209047. [7] Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Comput., 22(5-6):363–379, 2010. [8] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM, 63(3), June 2016. Conference version: IEEE FOCS 2012. [9] Béla Bollobás. Distinguishing vertices of random graphs. In Annals of Discrete Mathematics, volume 13 of North-Holland Mathematics Studies, pages 33–49. North-Holland, 1982. doi: 10.1016/S0304-0208(08)73545-X. [10] Soumyottam Chatterjee, Gopal Pandurangan, and Nguyen Dinh Pham. Distributed MST: A smoothed analysis. In Proceedings of the 21st International Conference on Distributed Computing and Networking, pages 1–10, 2020. [11] Fan Chung and Linyuan Lu. The diameter of sparse random graphs. Adv. Appl. Math., 26(4):257–279, 2001. URL: https://doi.org/10.1006/aama.2001.0720, doi:10.1006/ AAMA.2001.0720. 40

[12] Tomek Czajka and Gopal Pandurangan. Improved random graph isomorphism. J. Discrete Algorithms, 6(1):85–92, 2008. URL: https://doi.org/10.1016/j.jda.2007.01.002, doi: 10.1016/J.JDA.2007.01.002. [13] Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport. Smoothed analysis of dynamic networks. Distributed Computing, 31(4):273–287, August 2018. doi:10.1007/ s00446-017-0300-8. [14] Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, and Calvin Newport. Smoothed analysis of information spreading in dynamic networks. J. ACM, 71(3):17, 2024. doi:10.1145/3661831. [15] Julia Gaudio, Miklós Z. Rácz, and Anirudh Sridhar. Average-case and smoothed analysis of graph isomorphism. The Annals of Applied Probability, 35(2):1373 – 1406, 2025. doi: 10.1214/25-AAP2146. [16] Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 270– 277. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch20, doi:10.1137/ 1.9781611974331.CH20. [17] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2148–2179. IEEE, 2024. doi:10.1109/FOCS61266.2024.00007. [18] Mohsen Ghaffari, Christoph Grunau, and Václav Rozhon. Improved deterministic network decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2904–2923, 2021. [19] Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Robust shattering arguments. CoRR, abs/2606.27847, 2026. URL: https://doi.org/10.48550/arXiv. 2606.27847, arXiv:2606.27847, doi:10.48550/ARXIV.2606.27847. [20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. J. ACM, 71(3):19, 2024. doi:10.1145/3656638. [21] Seri Khoury and Aaron Schild. Round elimination via self-reduction: Closing gaps for distributed maximal matching. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 2292–2305. IEEE, 2025. doi:10.1109/FOCS63196.2025.00120. [22] Seri Khoury and Aaron Schild. No truly sublogarithmic-round algorithm for distributed mis in the local model, 2026. URL: https://arxiv.org/abs/2610.18215, arXiv:2610.18215. [23] K. Krzywdziński and K. Rybarczyk. Distributed algorithms for random graphs. Theoretical Computer Science, 605:95–105, 2015. URL: https://www.sciencedirect.com/science/ article/pii/S0304397515007847, doi:10.1016/j.tcs.2015.08.037. [24] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2), 2016. [25] Christoph Lenzen and Roger Wattenhofer. MIS on trees. In ACM PODC, pages 41–48, 2011. 41

[26] Nati Linial and Jonathan Mosheiff. On the rigidity of sparse random graphs. J. Graph Theory, 85(2):466–480, 2017. URL: https://doi.org/10.1002/jgt.22073, doi:10.1002/ JGT.22073. [27] Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036–1053, 1986. Conference version: ACM STOC 1985. [28] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603. [29] David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, 2000. [30] Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 350–363, 2020. [31] Johannes Schneider and Roger Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 35–44. ACM, 2008. [32] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385–463, May 2004. URL: http://doi.acm.org/10.1145/990308.990310, doi:10.1145/990308.990310. [33] Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Communications of the ACM, 52(10):76–84, October 2009. URL: http://doi.acm.org/10.1145/1562764.1562785, doi:10.1145/1562764.1562785.

A

Proof of Lemma 2.2

We prove Lemma 2.2 with c′ = 1024. Let X ∼ G(N, q) with 0 < q ≤ 1/2 and ν = N q ≥ 1024(ln N + 1). In particular ν ≥ 1024 and ln N + 1 ≤ ν/1024. Put 

b0 = ⌊1/q⌋ ,

 ln N r= + 1. ln(ν/8)

For a vertex set U , its external neighbors are the vertices of NX (U )\U . The proof uses the following two properties of X. (P1) Small sets expand: every vertex set U with 1 ≤ |U | ≤ b0 has at least ν |U | /8 external neighbors. (P2) Large sets are adjacent: any two disjoint vertex sets U, W with |U | , |W | ≥ ⌈N/16⌉ are joined by an edge of X. Lemmas A.1 and A.2 show that each property fails with small probability, and Lemma A.3 shows that together they bound the diameter. Lemma A.1. P[(P1) fails] ≤ 2e−ν/64 . 42

Proof. One fixed set. Fix U with |U | = b, where 1 ≤ b ≤ b0 . Since b0 ≤ 1/q = N/ν ≤ N/2, there are N − b ≥ N/2 vertices outside U . Each of them is an external neighbor of U independently, with probability qb 1 − (1 − q)b ≥ 1 − e−qb ≥ . 2 The first inequality uses 1 − q ≤ e−q . For the second, put y = qb; then 0 < y ≤ 1 because b ≤ b0 ≤ 1/q, and e−y ≤ 1−y+y 2 /2 ≤ 1−y/2 for 0 ≤ y ≤ 1. Hence the number of external neighbors is a sum of independent indicators with mean at least (N/2)(qb/2) = νb/4. By Fact 2.1(F2) with δ = 1/2, h νb i P |NX (U ) \ U | < ≤ e−νb/32 . 8
All sets of one size. There are Nb ≤ (eN/b)b ≤ eb(ln N +1) ≤ eνb/1024 sets of size b. By a union bound, some set of size b fails to expand with probability at most eνb/1024 e−νb/32 ≤ e−νb/64 , since 1/32 − 1/1024 ≥ 1/64. All sizes. Property (P1) fails exactly when some set of some size b ∈ {1, . . . , b0 } fails to expand. Put y = e−ν/64 . Since ν ≥ 1024, we have y ≤ e−16 ≤ 1/2. Summing over b ≥ 1, P[(P1) fails] ≤

X b≥1

yb =

y ≤ 2y = 2e−ν/64 . 1−y

Lemma A.2. P[(P2) fails] ≤ e−νN/512 . Proof. One fixed pair. Fix disjoint sets U, W with |U | , |W | ≥ ⌈N/16⌉. There are |U |·|W | ≥ N 2 /256 vertex pairs with one end in U and the other in W , and each is an edge of X independently with probability q. So no edge joins U and W with probability at most 2

2

(1 − q)N /256 ≤ e−qN /256 = e−νN/256 . Counting the pairs. An ordered pair (U, W ) of disjoint sets is determined by deciding, for each of the N vertices, whether it lies in U , in W , or in neither. So there are at most 3N such pairs. Union bound. Hence P[(P2) fails] ≤ 3N e−νN/256 = e−N (ν/256−ln 3) ≤ e−νN/512 , since ν/512 ≥ 2 > ln 3 gives ν/256 − ln 3 ≥ ν/256 − ν/512 = ν/512. Lemma A.3. If X has properties (P1) and (P2), then diam(X) ≤ 2r + 1. Proof. For a vertex v and an integer i ≥ 0, let Balli (v) be the set of vertices at distance at most i from v in X. A vertex is at distance at most i + 1 from v exactly when it lies in Balli (v) or is an external neighbor of Balli (v). Fix a vertex v. Small balls grow fast. If |Balli (v)| < b0 , then (P1) applies to Balli (v), and  ν ν |Balli+1 (v)| ≥ 1 + |Balli (v)| ≥ |Balli (v)| . 8 8 In particular, a ball with fewer than b0 vertices gains a vertex in each step. Since X has N ≥ b0 vertices, there is a first index i∗ with |Balli∗ (v)| ≥ b0 . Since q ≤ 1/2, we have b0 ≥ 2, so i∗ ≥ 1. 43

The ball reaches b0 vertices by radius r − 1. By induction, |Balli (v)| ≥ (ν/8)i for all i ≤ i∗ . Applying this at i = i∗ − 1, where the ball still has fewer than b0 vertices,  ν i∗ −1 8

≤ |Balli∗ −1 (v)| < b0 ≤ N.

Taking logarithms, i∗ − 1 < ln N/ ln(ν/8), so i∗ ≤ ⌈ln N/ ln(ν/8)⌉ = r − 1. One more step reaches N/16 vertices. Choose U ⊆ Balli∗ (v) with exactly b0 vertices. By (P1), U has at least νb0 /8 external neighbors, and all of them lie in Balli∗ +1 (v). Since 1/q ≥ 2 and ⌊y⌋ ≥ y/2 for y ≥ 2, we have b0 ≥ 1/(2q), so |Ballr (v)| ≥ |Balli∗ +1 (v)| ≥

νb0 ν N ≥ = , 8 16q 16

using i∗ + 1 ≤ r. As the left-hand side is an integer, |Ballr (v)| ≥ ⌈N/16⌉. Any two vertices are close. Let u, v be vertices. If Ballr (u) and Ballr (v) share a vertex, then distX (u, v) ≤ 2r. Otherwise they are disjoint, each with at least ⌈N/16⌉ vertices, so by (P2) some edge xy has x ∈ Ballr (u) and y ∈ Ballr (v), and distX (u, v) ≤ r + 1 + r. In both cases distX (u, v) ≤ 2r + 1. Proof of Lemma 2.2. By Lemma A.3, the diameter exceeds 2r + 1 only if (P1) or (P2) fails. Since ν = N q ≥ 1024 and q ≤ 1/2, we have N ≥ 2048, so νN/512 ≥ ν/64. By Lemmas A.1 and A.2,   ′ P diam(X) > 2r + 1 ≤ 2e−ν/64 + e−νN/512 ≤ 3e−ν/64 ≤ 3e−ν/1024 = 3e−ν/c .

44

Related documents

• Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover#1402185
• An $\tilde Ω(\log n \log m)$ Information-Theoretic Lower Bound for Randomized Online Set Cover#1034420
• A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces#1648481
• Lower Bounds for Moments of $L$-functions#927459
• Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set#173252