Pith.

Distributed, Parallel, and Cluster Computing · arXiv:2611.16302 v1 · submitted 12 Nov 2026 · 35 references

Smoothed Analysis for Distributed MIS

Dipan Dey, Fabien Dufoulon, William K. Moses Jr., Gopal Pandurangan

The paper says

“We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem.”

more of the abstract

Luby's algorithm computes an MIS in O(logn) rounds, while the recent Ω(logn/loglogn) lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph G on n nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where G(n,p) is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability p. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph G, when p = βlnn/n for a sufficiently large constant β, a randomized LOCAL algorithm, given only 𝒢s, computes an MIS of 𝒢s in O(√(logn)) rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if p ≤ (1/2−δ)lnn/n for a fixed constant δ > 0, there exists a base graph on which every randomized LOCAL MIS algorithm requires Ω(logn/loglogn) rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions.

4 major objections · 10 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 35 references say.

The paper says, at Section 5 (lower bound), specifically Lemma 5.7 and Theorem 5.8

The review did not quote this passage.

Pith says: Objection 1 of 4 · major

The lower bound (Theorem 5.8) depends critically on the unpublished Khoury–Schild preprint [22] (arXiv:2610.18215, October 2026). The authors acknowledge this in Section 1.3 and the AI disclosure, but the result is load-bearing: without it, the matching lower bound collapses to Ω(√log n) [21], which would not match the O(√log n) upper bound.

more of objection 1

The paper does not provide any independent verification or alternative proof of the Khoury–Schild bound. While citing an unpublished preprint is permissible, the referee must note that the lower bound is conditional on the correctness and applicability of [22]. If [22] is later retracted or found to have a flaw, the central claim of near-optimal smoothing is unsupported. The authors should discuss this dependency more explicitly and perhaps include a note that the lower bound holds assuming the Khoury–Schild result.

The paper says, at Section 1.5 (Model) and Section 4.1 (Algorithm)

The review did not quote this passage.

Pith says: Objection 2 of 4 · major

The model statement in Section 1.5 says: '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).'

more of objection 2

However, the algorithm in Section 4.1 computes λ = β ln n and uses it to set parameters B, θ, ℓ. Since p = λ/n, the algorithm effectively knows p (up to the constant β). The authors should clarify whether the algorithm knows β or p. If the algorithm knows n and the constant β (which is part of the algorithm design), then it knows p = β ln n / n. This seems to contradict the model statement that nodes do not know p. The authors should either adjust the model to allow knowledge of p (or β) or explain how the algorithm can compute these parameters without knowing p. This is a tension between the model and the algorithm.

The paper says, at Section 4.2.1, Lemma 4.5 and the case analysis

The review did not quote this passage.

Pith says: Objection 3 of 4 · major

The proof of Lemma 4.5 splits into cases based on properties of the base graph G alone (M, z_H, z_Q). The algorithm does not know these quantities, but the analysis shows that regardless of which case holds, condition (1) holds w.h.p.

more of objection 3

This is fine. However, the proof uses the event E (Lemma 4.6) that every vertex has at most 2λ incident random edges. The failure probability of E is n^{1-β/3}. The constant β is chosen as 2a with a ≥ 48(c+3). This ensures the failure probability is small. But the analysis also uses Lemma 3.1 and Lemma 3.5, which require certain conditions on s, t, etc. The authors should verify that all constants are consistent and that the union bounds over the cases do not miss any scenario. The case analysis seems exhaustive, but the presentation is dense and could benefit from a clearer summary of how the cases cover all possibilities.

The paper says, at Section 4.3 (Extension to symmetric difference model)

The review did not quote this passage.

Pith says: Objection 4 of 4 · major

The extension to the symmetric difference model (G_s = G △ G(n,p)) is argued by considering a random subgraph G' of G and then smoothing G'. The argument is brief and relies on the fact that the algorithm works for every base graph, in particular for every outcome of G'.

more of objection 4

However, the distribution of G' is defined as keeping each edge of G independently with probability γ = (1-2p)/(1-p). The authors claim that G' smoothed (additions only) has the same distribution as G △ G(n,p). This is a standard coupling, but the authors should provide a brief justification or cite a known result. The current explanation is somewhat terse and may be confusing.

10 minor objections

The paper says, at General

Pith says: minor objection 1 of 10

The paper uses both natural log and log base 2; it would be helpful to state explicitly that all logarithms are natural unless otherwise noted (they do state this in Section 2, but it could be repeated in the abstract or introduction).

The paper says, at Section 1.5

Pith says: minor objection 2 of 10

The model description says 'We assume that each node has a distinct ID of size O(log n) bits.' This is standard. However, the lower bound construction assigns IDs exactly in [n]. The authors should note that this is without loss of generality for the lower bound.

show 8 more

The paper says, at Section 2, Lemma 2.2

Pith says: minor objection 3 of 10

The constant c' is set to 1024 in the appendix proof, but in the main text it is referred to as an absolute constant. It would be helpful to state the value explicitly in the lemma statement for clarity.

The paper says, at Section 3.2, Lemma 3.5

Pith says: minor objection 4 of 10

The statement of Lemma 3.5 includes the condition 'ln Δ = O(√log n)' and 'k = O(log n)'. These conditions are used in the 'in particular' part. The lemma itself is more general. The authors should separate the general bound from the asymptotic simplification.

The paper says, at Section 4.1, Algorithm 1

Pith says: minor objection 5 of 10

The algorithm uses a deterministic rule to compute an MIS of a component (e.g., greedy by ID). This is fine, but the authors should note that this rule is applied locally by each active vertex after gathering. Since the component is known, all vertices in the component compute the same MIS. This is already implied, but could be stated more explicitly.

The paper says, at Section 4.2.1, Lemma 4.9

Pith says: minor objection 6 of 10

The event E_0 depends on the random edges inside L_0. The proof uses a union bound over two properties. The bound for property (b) uses the fact that z_H < n/√B_0. This is valid in Case (2b). The authors should ensure that the proof of Lemma 4.9 does not implicitly assume any condition that is not guaranteed in Case (2b).

The paper says, at Section 5.2, Lemma 5.5

Pith says: minor objection 7 of 10

The bound on E[X] uses max{1, np}^{T+2}. Since p ≤ (1/2-δ) ln n / n, np ≤ (1/2-δ) ln n, which is >1 for large n. So max{1, np} = np. The bound is then (np)^{T+2} ≤ (ln n)^{T+2}. The authors should clarify this.

The paper says, at Section 5.2, Lemma 5.6

Pith says: minor objection 8 of 10

The coupling argument is described at a high level. The authors should ensure that the probability of mismatch is correctly bounded. The term ps^2 appears, and s = ⌊n^α⌋ with α < 1/2, so ps^2 = O(n^{2α-1} log n) = o(1). This is fine.

The paper says, at AI Disclosure

Pith says: minor objection 9 of 10

The AI disclosure states that ChatGPT produced most of the technical results. The authors say they significantly reworked the proofs and exposition. This is unusual but not prohibited. The referee should evaluate the paper on its merits. The disclosure does not affect the technical assessment.

The paper says, at References

Pith says: minor objection 10 of 10

Reference [19] is an arXiv preprint (2606.27847) from 2026. The authors should ensure that all references are correctly cited and that the most recent versions are used.

What would settle it

Independently verify the Khoury–Schild lower bound [22] for the specific regime needed: does it hold for every randomized LOCAL algorithm that succeeds with constant probability (e.g., 0.9) on all n-node graphs? If the proof in [22] contains a flaw or applies only to algorithms with success probability 1 - 1/n, then the reduction in Section 5.3 fails and the lower bound of Theorem 5.8 is invalid. A concrete check: re-derive the key lemma of [22] that constructs a hard graph family and show that any o(log n / log log n)-round algorithm has success probability at most 1/2 on that family. If this cannot be done, the present paper's lower bound is unsupported.

from the skeptic's reading

How the review went

3 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic agrees 9 s · 45,956 tokens read, 930 written
  3. Referee major revision: 4 major objections, 10 minor 18 s · 46,335 tokens read, 2,169 written

Not run on this paper: the editor, the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The strongest objection

The paper's central claim of near-optimal smoothing requires both an upper bound (Theorem 4.14) and a matching lower bound (Theorem 5.8). The lower bound is a reduction from MIS on an arbitrary h-node graph H to MIS on the smoothed graph G, and it invokes the Omega(log h / log log h) randomized LOCAL MIS lower bound of Khoury and Schild [22] (arXiv:2610.18215, October 2026). This source is an unpublished preprint that appeared only weeks before the present paper. The authors themselves note (Section 1.3) that the previous best lower bound was Omega(sqrt(log n)) [21], and that [22] is a 'major breakthrough' announced in October 2026. If [22] is incorrect, does not hold for constant success probability, or is later retracted, then Theorem 5.8 no longer provides a matching lower bound: the best known lower bound for MIS on the constructed smoothed graph would revert to Omega(sqrt(log n)) [21], which is far below the O(sqrt(log n)) upper bound, and the claim of optimal smoothing (up to a constant factor) is unsupported. The paper acknowledges this fragility in the reader's weakest_assumption and in the AI disclosure, but does not mitigate it. The lower bound is load-bearing because without it the paper's main message reduces to 'smoothing with p = Theta(log n / n) yields O(sqrt(log n)) rounds', which is interesting but not nearly as strong as the claimed near-tightness.

The reader's verdict is CONDITIONAL, and the weakest_assumption explicitly flags the dependence on the unpublished Khoury–Schild lower bound. I agree that this is the single most load-bearing concern. The upper bound (Theorem 4.14) is a self-contained contribution and appears technically sound, but the paper's headline claim of 'nearly tight bounds' and 'optimal up to a constant factor' rests on the lower bound matching the upper bound. If the Khoury–Schild result is incorrect or inapplicable, the lower bound reverts to Omega(sqrt(log n)) [21], which does not match the O(sqrt(log n)) upper bound—the smoothing parameter would still be optimal for achieving O(sqrt(log n)) rounds, but the lower bound would no longer show that less smoothing gives no advantage (the lower bound would be weaker). The paper acknowledges this dependence (Section 1.3, Section 5.3) and the AI disclosure adds a layer of uncertainty, but the authors do not provide an independent proof or a conditional statement that separates the lower bound from [22]. The concrete test I propose is to independently verify the Khoury–Schild lower bound for the required regime. Until that is done, the verdict should remain CONDITIONAL, as the reader recommended. I see no other concern that is as load-bearing: the model inconsistency about knowledge of p (Section 1.5 vs. Section 4.1) is acknowledged by the reader and can be resolved by a clarification; the AI disclosure is a meta-concern but does not directly affect mathematical correctness. The lower bound dependence is the critical unresolved issue.

The referee's report

If the results are correct, this is a significant contribution to distributed graph algorithms. It introduces smoothed analysis to a fundamental local problem (MIS) and provides nearly tight bounds on the amount of smoothing needed to overcome worst-case lower bounds. The upper bound algorithm is non-trivial and uses a combination of degree classification, helper selection, gathering, and a black-box MIS algorithm. The lower bound is a reduction that leverages the recent (unpublished) Khoury–Schild lower bound. The paper is well-structured and the proofs are detailed. The main strength is the tight characterization of the smoothing threshold.

Pith's reading of the paper (a machine's summary, not the authors')

The paper establishes that a small amount of random edge perturbation (smoothing) can dramatically speed up distributed computation of a maximal independent set (MIS) in the LOCAL model. For any worst-case input graph, adding or deleting each edge independently with probability p = Θ(ln n / n) reduces the round complexity from the tight worst-case lower bound of Ω(log n / log log n) down to O(√log n). This shows that the known worst-case barrier for distributed MIS is fragile: it can be overcome by a tiny amount of randomness. The authors also prove that this amount of smoothing is essentially optimal: if p ≤ (1/2 − δ) ln n / n, there exists a base graph on which every randomized LOCAL algorithm still requires Ω(log n / log log n) rounds.

What carries the argument. The upper bound algorithm partitions vertices into high-degree and low-degree categories using a threshold B = Θ($e^{{√log n}}$) and proceeds in three steps: (1) low-degree vertices become 'helpers' that dominate many high-degree vertices through random marked edges; (2) the remaining 'active' high-degree vertices gather their components in O(√log n) rounds using the fact that the random edges have reduced the diameter of the active subgraph to O(√log n); (3) the leftover low-degree subgraph, which has bounded degree, is handled by a standard O(log Δ) MIS algorithm. The lower bound constructs a base graph from an arbitrary input graph H by replacing each node with a clique of size k and adding isolated padding nodes, then shows that if p is too small, any MIS algorithm on the smoothed graph can be simulated back on H without significant overhead, inheriting the Ω(log n / log log n) lower bound of Khoury and Schild.

Core claim. For every base graph G and every constant c, there exists a constant β such that when the smoothed graph G_s = G △ G(n, p) has p = β ln n / n, a randomized LOCAL algorithm can compute an MIS of G_s in O(√log n) rounds with high probability. Conversely, if p ≤ (1/2 − δ) ln n / n for any fixed δ > 0, there exists a base graph on which every randomized LOCAL MIS algorithm requires Ω(log n / log log n) rounds. Thus the smoothing threshold for achieving a near-quadratic speedup is Θ(ln n / n), tight up to a constant factor.

The premise it rests on. The lower bound relies on the unpublished result of Khoury and Schild (arXiv 2610.18215) that any randomized LOCAL algorithm for MIS requires Ω(log n / log log n) rounds on some graphs; if that result is incorrect, does not apply to constant success probability, or is retracted, the matching lower bound collapses.

If the paper is right (Pith's inferences, not the authors')

The worst-case lower bound for distributed MIS is fragile: adding Θ(n log n) random edges to any graph breaks the hardness and allows a near-quadratic speedup.

The smoothing threshold is tight up to a constant factor: smoothing with fewer than about (1/2) n log n random edges cannot guarantee any speedup for all base graphs.

The results extend to the symmetric-difference model (both edge additions and deletions) with the same parameters.

The algorithm does not need to know which edges are random or the smoothing parameter p, making it applicable in realistic settings where the base graph is unknown.

The lower bound holds even if nodes know p and can distinguish original edges from random edges, showing the hardness is intrinsic to the amount of randomness, not the knowledge.

The O(√log n) round complexity may itself be improvable; the paper notes that even for pure G(n,p) random graphs no faster algorithm or matching lower bound is known, so the √log n barrier might be a consequence of the current analysis rather than a fundamental limit.

The structural lemma about smoothed diameter (Lemma 3.1) could be applied to other distributed local problems that benefit from small diameter, such as maximal matching or coloring, suggesting a general recipe for smoothed analysis of local graph algorithms.

The lower bound construction uses a reduction that may extend to other symmetry-breaking problems, indicating that the Θ(ln n / n) smoothing threshold might be universal for problems that are hard on graphs with large treewidth or high degree.

The paper's algorithmic approach (helpers + gathering + bounded-degree completion) could be adapted to the CONGEST model if the gathering primitive can be replaced by a bandwidth-efficient broadcast, though the current analysis relies on unbounded message size.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in O(logn) rounds, while the recent Ω(logn/loglogn) lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph G on n nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where G(n,p) is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability p. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph G, when p = βlnn/n for a sufficiently large constant β, a randomized LOCAL algorithm, given only 𝒢s, computes an MIS of 𝒢s in O(√(logn)) rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if p ≤ (1/2−δ)lnn/n for a fixed constant δ > 0, there exists a base graph on which every randomized LOCAL MIS algorithm requires Ω(logn/loglogn) rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-13

The authors' main claim, as the classifier picked it out 0.98

“These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.69 · human participants 0.01 · controlled comparison 0.26 · randomized assignment 0.40 · states quantitative result 0.99 · compares with prior results 0.96 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. contribution 0.91 0.70 0.03 asserted 0.70
Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $\Omega(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. background 1.00 0.04 0.04 asserted 1.00
We ask whether small random perturbations can overcome this worst-case barrier. gap 0.95 0.09 0.04 unclear 0.57
Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. method 0.94 0.63 0.04 asserted 0.91
Thus, each possible edge is independently toggled with probability $p$. method 1.00 0.27 0.02 asserted 1.00
We establish nearly tight bounds on the smoothing needed for faster distributed MIS. contribution 0.70 0.94 0.30 asserted 1.00
For every base graph $G$, when $p=\beta\ln n/n$ for a sufficiently large constant $\beta$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. result 1.00 0.95 0.46 asserted 1.00
This is almost quadratically faster than the worst-case lower bound. interpretation 0.87 0.81 0.14 asserted 1.00
Conversely, if $p\le(1/2-\delta)\ln n/n$ for a fixed constant $\delta>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $\Omega(\log n/\log\log n)$ rounds on the smoothed graph. result 1.00 0.87 0.15 asserted 1.00
Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. interpretation 0.54 0.92 0.24 asserted 1.00
These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems. interpretation 1.00 0.82 0.86 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 8,319 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (8)
Figure 1 of the paper
Figure 1. The construction in the proof of Lemma 3.2, with
Figure 2 of the paper
Figure 2. Algorithm 1 on a small example. Filled vertices are high and hollow vertices are low;
Figure 3 of the paper
Figure 3. The case analysis in the proof of Lemma 4.5. Each test depends only on the base graph
Figure 4 of the paper
Figure 4. Case (2b), seen from a base-high vertex h. Grey vertices form the sample Bh: the base￾low vertices outside X0 joined to h by a marked random edge (red, dashed). Sampled vertices in X + 0 , 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)
Figure 5 of the paper
Figure 5. An illustrative assignment of virtual nodes to
Figure 6 of the paper
Figure 6. Construction and simulation in the reduction. The input graph
Figure 7 of the paper
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
Figure 8 of the paper
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,…

Figures are the authors', reproduced from the paper.

References (35)
  1. [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 on PithPith's reviewarXiv
  2. [21] Seri Khoury and Aaron Schild. Round elimination via self-reduction: Closing gaps for dis- tributed maximal matching. In66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 2292–2305. IEEE, 2025. doi:10.1109/FO... on Pithdoi:10.1109/focs63196.2025.00120
  3. [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 on Pithdoi:10.1016/j.ejc.2025.104152
  4. [2] Noga Alon, L´ aszl´ o 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 on Pith
  5. [3] Michael Anastos, Matthew Kwan, and Benjamin Moore. Smoothed analysis for graph isomor- phism. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2098–2106, 2025 on Pith
  6. [4] L´ aszl´ o 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– on Pith
  7. [5] L´ aszl´ o 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, ... on Pithdoi:10.1145/3313276.3316356
  8. [6] L´ aszl´ o Babai, Paul Erd˝ os, and Stanley M. Selkow. Random graph isomorphism.SIAM J. Comput., 9(3):628–635, 1980.doi:10.1137/0209047 on Pithdoi:10.1137/0209047
  9. [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 on Pith
  10. [8] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of dis- tributed symmetry breaking.Journal of the ACM, 63(3), June 2016. Conference version:IEEE FOCS2012 on Pith
  11. [9] B´ ela Bollob´ as. Distinguishing vertices of random graphs. InAnnals of Discrete Mathematics, volume 13 ofNorth-Holland Mathematics Studies, pages 33–49. North-Holland, 1982.doi: 10.1016/S0304-0208(08)73545-X on Pithdoi:10.1016/s0304-0208(08)73545-x
  12. [10] Soumyottam Chatterjee, Gopal Pandurangan, and Nguyen Dinh Pham. Distributed MST: A smoothed analysis. InProceedings of the 21st International Conference on Distributed Computing and Networking, pages 1–10, 2020 on Pith
  13. [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 on Pithdoi:10.1006/aama.2001.0720
  14. [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 on Pithdoi:10.1016/j.jda.2007.01.002
  15. [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 on Pith
  16. [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 on Pithdoi:10.1145/3661831
  17. [15] Julia Gaudio, Mikl´ os Z. R´ acz, 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 on Pithdoi:10.1214/25-aap2146
  18. [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, V A, USA, January 10-12, 2016, pages 270– on Pith
  19. [17] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In65th 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/F... on Pithdoi:10.1109/focs61266.2024.00007
  20. [18] Mohsen Ghaffari, Christoph Grunau, and V´ aclav Rozhon. Improved deterministic network decomposition. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2904–2923, 2021 on Pith
show 15 more
  1. [19] Mohsen Ghaffari, Magn´ us M. Halld´ orsson, Yannic Maus, and Alexandre Nolin. Robust shat- tering arguments.CoRR, abs/2606.27847, 2026. URL:https://doi.org/10.48550/arXiv. 2606.27847,arXiv:2606.27847,doi:10.48550/ARXIV.2606.27847 on PithPith's reviewarXivdoi:10.48550/arxiv.2606.27847
  2. [20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries.J. ACM, 71(3):19, 2024.doi:10.1145/3656638 on Pithdoi:10.1145/3656638
  3. [23] K. Krzywdzi´ nski and K. Rybarczyk. Distributed algorithms for random graphs.Theoreti- cal Computer Science, 605:95–105, 2015. URL:https://www.sciencedirect.com/science/ article/pii/S0304397515007847,doi:10.1016/j.tcs.2015.08.037 on Pithdoi:10.1016/j.tcs.2015.08.037
  4. [24] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds.Journal of the ACM, 63(2), 2016 on Pith
  5. [25] Christoph Lenzen and Roger Wattenhofer. MIS on trees. InACM PODC, pages 41–48, 2011. 41 on Pith
  6. [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 on Pithdoi:10.1002/jgt.22073
  7. [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 on Pith
  8. [28] Michael Mitzenmacher and Eli Upfal.Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.doi:10.1017/CBO9780511813603 on Pithdoi:10.1017/cbo9780511813603
  9. [29] David Peleg.Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, 2000 on Pith
  10. [30] V´ aclav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposi- tion and distributed derandomization. In52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 350–363, 2020 on Pith
  11. [31] Johannes Schneider and Roger Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. InProceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 35–44. ACM, 2008 on Pith
  12. [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 on Pithdoi:10.1145/990308.990310
  13. [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 pro... on Pithdoi:10.1145/1562764.1562785
  14. [277] SIAM, 2016. URL:https://doi.org/10.1137/1.9781611974331.ch20,doi:10.1137/ 1.9781611974331.CH20 on Pithdoi:10.1137/1.9781611974331.ch20
  15. [697] ACM, 2016.doi:10.1145/2897518.2897542 on Pithdoi:10.1145/2897518.2897542

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment