No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model

No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model Seri Khoury∗

Aaron Schild†

arXiv:2610.18215v1 [cs.DS] 13 Oct 2026

October 14, 2026

Abstract We prove that o( logloglogn n )-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the 40-year-old O(log n)-round randomized CONGEST algorithm of Luby and Alon, Babai, and Itai is nearly optimal. Our lower √ bound improves upon the Ω( log n)-round lower bound of Khoury and q Schild and nearly closes the

20+ year-old gap between the O(log n)-round algorithm and the Ω( logloglogn n )-round lower bound of Kuhn, Moscibroda, and Wattenhofer. To close this gap, one must show a lower bound for a graph that is not locally treelike. We do this by starting with a D-regular, Θ(logD n)-girth graph, with D = Θ(log n). Crucially, this is not our final graph. We obtain our hard instance by replacing each vertex of this treelike graph with a clique on nc vertices for some constant c ∈ (0, 1). We then replace each edge with a bipartite Erdős–Rényi graph between the corresponding cliques, with each edge present independently with probability 1/2. Intuitively, finding an MIS is challenging in this graph because it blocks the classic shattering phenomenon that underpins many algorithms in distributed computing. Roughly speaking, one round of Luby/ABI does not appreciably affect the structure of our hard instance. A clique is occupied by an independent set vertex with probability Θ(1/D), causing only an additive decrease in the maximum degree of the connectivity graph between cliques. This is in contrast with its effect on ∆-regular trees, where it achieves a constant-factor multiplicative reduction in the maximum degree of the tree. We extend this intuition to arbitrary LOCAL algorithms via a novel round elimination approach on our non-treelike hard instance. We describe algorithms that output a set of vertices in this graph using two metrics: their occupancy probability and their conflict probability. Our round elimination framework takes an r-round algorithm and produces an (r − 1)-round algorithm where occupancy and conflict probabilities collectively slightly degrade, but individually can significantly improve or degrade. This round elimination result is obtained by exploiting the lack of large biclique complements in dense bipartite Erdős–Rényi graphs, which in turn allows us to bound the entropy of the output distribution for any independent set algorithm.

∗ Cognifence. seri.khoury@cognifence.ai

† Google Research. aaron.schild@gmail.com

1

Contents 1 Introduction 1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 5

2 Technical Overview 2.1 The Hard Instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The Occupancy Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 The One Round Warmup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Ω̃(D1/3 )-Round Lower Bound via Round Elimination . . . . . . . . . . . . . . . 2.2.3 Ω̃(D1/2 )-Round Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 The Main Ω(D/(log D))-Round Lower Bound . . . . . . . . . . . . . . . . . . . . 2.3 From the Occupancy Theorem to LOCAL . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Outline and Reading Advice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6 7 8 8 8 9

3 From the Occupancy Bound to Randomized LOCAL

9

4 Preliminaries 11 4.1 Radius-s Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Table of Parameters and Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5 Warmup: One-Round Hardness 14 5.1 1-Round Algorithms have Short Output Lists . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 Short Lists Imply Low Occupancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6 Round Elimination by Conditional Resampling

17

7 Multi-Round Entropy Bounds 18 7.1 Single-Layer Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.2 Multiple Layers via Telescoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7.3 Implications for Local Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 8 Obtaining Shortlists via Round Elimination 20 8.1 Conflict Probability Bounds Edge Tails . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 8.2 Edge Tails Bound Vertex Tails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.3 Sandwiching Vertex Tails between Occupancy and Conflict via Entropy . . . . . . . . . 22 9 Warmups to the Final Bound 23 9.1 Consolidating One-Round Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9.2 First (Ω̃(D1/3 )) Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 9.3 Second (Ω̃(D1/2 )) Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 10 Exploiting Multi-Round Entropy Bounds 26 10.1 A Multi-Step Version of Proposition 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 10.2 Combining Truncation Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 10.3 Improved Bound on S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 11 Proof of the Final Bound

28

12 AI Usage

29

A Details of the LOCAL Reduction 32 A.1 Extracting IDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.2 Producing Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.3 Extracting a Contradictory ID Assignment . . . . . . . . . . . . . . . . . . . . . . . . . 33 A.4 Maximality and Finite Skeletons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 A.5 Reduction Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2

1

Introduction

In the LOCAL model of distributed computing, each vertex is an independent processor that is given (a) an O(log n)-bit node ID and (b) an infinite tape of random bits, where tapes are independent for different vertices and IDs are distinct. There are r communication rounds, after which all vertices have received all information from vertices within distance r. The vertices must solve the problem of interest using only this local information. One of the most extensively studied problems in distributed computing is the problem of finding a maximal independent set (MIS): a set of pairwise nonadjacent vertices that cannot be enlarged by adding another vertex [1–22]. Classical randomized algorithms of Luby [1] and Alon, Babai, and Itai [2] from 1986 find an MIS in O(log n) communication rounds with high probability in the LOCAL model, where n is the number of vertices. Although later algorithms substantially improved the runtime on special graph classes [6, 7, 23], O(log n) remains the best known worst-case bound p in terms of n alone for general graphs. Kuhn, Moscibroda, and Wattenhofer [8, 24] proved an√Ω( log n/ log log n) randomized lower bound. Recently, Khoury and Schild [25, 26] improved it to Ω( log n), using a lower bound for maximal matching on trees and a reduction to MIS. Despite 40 years of progress, whether MIS admits an o(log n)-round algorithm on general graphs remains open. In this work, we nearly close the gap: our lower bound rules out o(log n/ log log n) rounds and, in particular, O(log1−ε n) rounds for every fixed ε > 0. It leaves a factor of log log n between the upper and lower bounds. Theorem 1.1 (Randomized LOCAL lower bound). For every fixed σ ∈ (0, 1], there are constants cσ > 0 and nσ such that the following holds for every n ≥ nσ . Any randomized LOCAL algorithm that outputs an MIS with probability at least σ on every n-vertex graph requires at least cσ

log n log log n

rounds in the worst case. This holds even when identifiers are the numbers in [n], the algorithm knows n exactly, and the algorithm knows the maximum degree up to a constant factor.1 The high-girth barrier. The vast majority of lower bounds in the LOCAL model are proven for graphs that are locally treelike for the following reason.2 Consider the endpoints of an arbitrary tree edge. Fixing the common information for those endpoints leaves separate branches that do not interact. This structure underlies both the indistinguishability constructions of Kuhn, Moscibroda, and√Wattenhofer [8] and many round-elimination arguments. √ Furthermore, Ghaffari [6, 19, 27] gave a O( log n)-round MIS algorithm for graphs with girth Ω( log n). Consequently, a stronger MIS lower bound cannot be obtained by requiring every relevant LOCAL neighborhood to be a tree. Thus, a new hard instance is required. Overcoming the high-girth barrier. We construct our hard instance in two steps. First, we retain a regular high-girth graph H as a skeleton, with degree D = Θ(log n). Second, we replace every skeleton vertex v by a clique Cv of size k, and replace each skeleton edge uv by a bipartite Erdős–Rényi graph with edge probability 1/2. The resulting graph contains triangles inside every clique and many other short cycles. Neighborhoods of adjacent vertices can therefore overlap heavily, even though the skeleton neighborhoods are trees. Intuitively, this graph is hard because it blocks the shattering phenomenon present in many LOCAL algorithms (e.g. [6, 27]). Applying the first t rounds only reduces the degree of the skeleton graph by O(t) additively, requiring Θ(D) rounds to consume the entire graph. Arbitrary LOCAL algorithms could do clever operations that consume more degree per round. Theorem 1.1 shows that this is not possible. 1 Approximation is used here for a technicality: degrees are random since the graph is random.

√

2 The prior Ω(

log n) lower bound for MIS applies for line graphs of trees, which are not trees, but was obtained by studying maximal matching on trees.

3

The occupancy theorem. We prove Theorem 1.1 via a reduction to a statement (Theorem 1.2) that involves simpler types of algorithms that are essentially equivalent to LOCAL algorithms on our hard instance. For this part, the skeleton is the infinite rooted D-regular tree, and each clique has named vertices [k], which are also called coordinates. Let Guv ∈ {0, 1}k×k be the bipartite adjacency matrix at an oriented skeleton edge, with Gvu = GT uv . Entries on distinct undirected edges and within each matrix are independent fair bits. A radius-r rule sees the matrices on edges whose endpoints are both within skeleton distance r of its root. It returns a coordinate of its root clique, or 0 for no selection. The same rule is used everywhere and is unchanged by rooted isomorphisms preserving matrix entries and coordinate names. In particular, it has no skeleton identifiers or supplied order of branches/port numbering. It may use a private final draw; these draws are independent at different roots after all matrices are fixed. Section 4 gives the precise model. For adjacent skeleton vertices u, v and rule A, write p(A) = P[Av ̸= 0],

ϵ(A) = P[Au , Av ̸= 0, Guv (Au , Av ) = 1].

where Aw denotes the output of A on w. These are the occupancy and conflict probability of A respectively; symmetry makes them independent of the specified root or edge. An independent set rule has ϵ(A) = 0. This is our main technical result: Theorem 1.2 (Occupancy bound). There is an absolute constant D0 such that, for integers D ≥ D0 , k with D ≤ log k ≤ D2 , and r ≥ 1, every symmetric radius-r rule of Section 4 satisfying ϵ(A) = 0 obeys 

5000r log D p(A) ≤ min 1, D

 .

(1)

In particular, occupancy probability tends to zero whenever r = o(D/ log D) = o((log n)/(log log n)). By a union bound, the probability that a specified clique can be dominated by at most one vertex from each neighboring clique is at most (k +1)D exp(−k2−D ) ≤ 1/poly(n). Thus, with high probability, every MIS intersects every clique, so an algorithm for MIS with success probability at least β has occupancy probability at least (1 − 1/poly(n))β. This yields a contradiction whenever r = o((log n)/(log log n)). Section 3 proves Theorem 1.1 using Theorem 1.2 as a black box. The remaining main-text sections prove Theorem 1.2, beginning with a complete one-round warmup. The appendix supplies the details of the LOCAL reduction. We used AI in the production of this work. We discuss our use of AI immediately before the references.

1.1

Related Work

Round elimination replaces an algorithm using r rounds by one using r − 1 rounds for a suitably transformed problem. The lower bound for the distributed Lovász local lemma by Brandt, Fischer, Hirvonen, Keller, Lempiäinen, Rybicki, Suomela, and Uitto [28] developed this method through sinkless orientation. Brandt [29] subsequently gave an automatic transformation for locally checkable problems on sufficiently high-girth graphs. Balliu, Brandt, Hirvonen, Olivetti, Rabie, and Suomela [5] used it to prove tight dependence on the maximum degree for MIS and maximal matching in the relevant small-degree regimes. The also showed the result we have in this work for deterministic LOCAL algorithms. Further applications include exact degree dependence for bipartite maximal matching [30], lower bounds for ruling sets [16], MIS and relaxed dominating-set problems in trees [18], and coloring [17]. Khoury and Schild [25] developed a self-reduction for matching that preserves the problem and tracks the probability that a vertex remains unmatched. Our occupancy argument also removes information from local views, but its estimates concern coordinate distributions and conflicts across random matrices. Balliu, d’Amore, and Olivetti [31] recently generalized self-reduction through the classical round-elimination framework by changing the error quantity being measured. In this paper, we do extensive tracking of how much importance certain skeleton edges have to the final output of the algorithm. These importances are quantified using entropy, which was partly inspired by the work of Backhausz, Gerencsér, and Harangi [32].

4

1.2

Open Problems

While this paper nearly closes an important gap in our understanding of the complexity for MIS, many fundamental open problems related to MIS remain: Problem 1: What is the exact round complexity of MIS in the randomized LOCAL model as a function of n? In this paper, we give a lower bound of Ω((log n)/(log log n)) on this complexity. The classical O(log n) round algorithm [1, 2] remains unbroken in spite of being 40 years old. The precise complexity could be between these two extremes [23]. Problem 2: What is the complexity of MIS in other distributed computing models? While there are many distributed computing models, two are particularly relevant to this question: quantum LOCAL and deterministic LOCAL. It is unclear if this lower bound applies to quantum LOCAL, even on our hard instance. For deterministic LOCAL, an Ω((log n)/(log log n))-round hardness result was already known prior to this work [5] and an Õ(log5/3 n)-round algorithm is known [15]. Problem 3: What is the complexity of maximal matching and vertex cover in the randomized LOCAL model? The prior KMW lower bound [24] applies to both O(1)-approximate vertex cover and maximal matching, while the lower bound of Khoury and Schild [25] only applies √ to maximal matching. The lower bound in this paper applies to neither problem. Thus, the Θ̃( log n) gap remains for both problems.

2

Technical Overview

We now outline the techniques used to prove Theorem 1.1. We break up the discussion into three parts: describing the hard instance, the occupancy argument (Theorem 1.2), and the proof of the desired result (Theorem 1.1) given Theorem 1.2. At the end, we give a detailed outline of the paper. Note that the occupancy discussion precedes the reduction discussion in the technical overview, but the opposite is the case for the corresponding sections. We chose to discuss the occupancy theorem first as it contains all of the novelty in our argument. The reduction uses standard techniques.

2.1

The Hard Instance

Our hard instance is constructed as follows: 1. Use Lemma A.5 to construct a D-regular graph H with girth at least (logD n)/100. This constructs H by arguing that a edge-count-maximizing n-vertex graph with the required girth and maximum degree D is actually a regular graph with degree D. Alternatively, one can sample a random regular graph and argue that it has the required girth with positive probability. 2. Replace each vertex with a clique of size k = nc for some constant c ∈ (0, 1). 3. Replace each edge with a random bipartite graph, with each edge sampled independently with probability 1/2. Running one round of the classical algorithm [1, 2] on this graph has the following effects, roughly speaking: 1. A 1/D-fraction of cliques contain a selected vertex in expectation. 2. Each of those cliques gets deleted. 3. Every other clique reduces in size by a factor of roughly 2ℓ , where ℓ is the number of neighboring cliques that contain a selected vertex.

5

Roughly speaking, ℓ = Θ(1) and a large fraction of cliques have the same value of ℓ. Thus, applying one round of Luby/ABI roughly has the effect of (a) deleting a 1/D fraction of the cliques, reducing a typical skeleton vertex’s degree by D × 1/D = 1 and (b) reducing the size of most other cliques by the same constant factor. In particular, the graph is now a copy of the original, with k decreased multiplicatively and D decreased additively. Since k ≫ 2Θ(D) , the algorithm must take Ω(D) iterations. General LOCAL algorithms may have too many dependencies for this exact argument to work. We instead describe an argument based on round elimination that works by tracking occupancy probability and conflict probability.

2.2

The Occupancy Argument

Recall that an r-round rule consumes the matrices (random graphs) for each edge within distance r of a skeleton vertex v and outputs an integer between 0 and k inclusive, with 0 output if the rule picks no vertex from Cv . We build up to the final argument by considering the following steps, all of which are fully proven in our writeup:3 1. A standalone 1-round impossibility result for our hard instance 2. A roughly Ω(D1/3 )-round impossibility result using a weak round elimination result and a weak final bound 3. A roughly Ω(D1/2 )-round impossibility result using the same round elimination result, but an optimal final bound 4. The final Ω(D/(log D))-round impossibility result using a better round elimination result Each of these arguments contains variations of the same three steps, which we initially point out during the one-round warmup discussion. 2.2.1

The One Round Warmup

Consider a one round rule; i.e. a rule that consumes the D matrices for skeleton edges incident with a root and produces a number between 0 and k inclusive. The rule has zero conflict probability, so never outputs two adjacent vertices in two adjacent cliques. We analyze its behavior in three steps. 1. Short list given one fixed incident matrix (Lemma 5.1): At one round, adjacent cliques see a common matrix Guv . All their other input matrices are independent. Therefore, after fixing Guv , their outputs are independent random choices. If each endpoint still has many possible nonzero outputs, the possible choices contain a large rectangle of matrix entries. A typical random matrix has an edge in every such rectangle, essentially because k-vertex dense Erdős–Rényi graphs have maximum clique size O(log k). Since every pair of possible choices has positive conditional probability due to independence, this would create a conflict. Consequently, for most matrices, at least one endpoint has only O(log k) possible outputs. 2. Short list of possible outputs overall (Proposition 5.4): The endpoint with few possible outputs may depend on the matrix. Symmetry nevertheless says that a random incident matrix gives the root a short list with probability at least 1/2 − o(1). The D incident matrices are independent, so the resulting lists are independent. Every list that applies must contain the root’s realized nonzero output. A coordinate that appears in many independent short lists must, with high probability, belong to a single fixed short list (Lemma 5.2). This gives a fixed list of DO(1) coordinates containing almost every output. 3. Short list implies low occupancy via entropy (Lemma 5.5): A rule could concentrate on one coordinate, so list size alone does not bound occupancy. The additional observation is that the output has only a limited amount of information about its D independent Pincident matrices (Lemma 4.5). Entropy measures this information: for probabilities p1 , . . . , ps , it is i pi log(1/pi ). Independent 3 Some of the propositions and lemmas in this work are only used in the warmup. In all cases, they are simpler versions

of results that are used in the final proof.

6

inputs cannot each reveal a large fraction of the same limited information budget. By symmetry, a specified incident matrix accounts for at most a 1/D fraction of that budget. Imagine hiding every matrix and drawing a coordinate from the rule’s unconditional output probabilities. At two endpoints these new draws are independent of the shared matrix between them, so their conflict probability is exactly half the square of their occupancy. Hiding the matrix can increase conflict only by an amount controlled by the information it carried about the outputs (Lemma 4.2). A short list makes that amount small (Lemma 4.4). Combining the two estimates gives occupancy O(log D/D). Section 5 proves this entire one-round argument. 2.2.2

Ω̃(D1/3 )-Round Lower Bound via Round Elimination

We remove the outermost input layer one round at a time. For each fixed smaller view, keep its most probable coordinates and change other outputs to 0. We call this operation truncation. Then average the kept output probabilities over the hidden layer and draw independently from those averaged probabilities. Effectively, we are moving the randomness from the outermost shell into the center. This idea is called conditional resampling. This defines a rule using one fewer round and preserves the kept occupancy. There are two quantities to control. Truncation loses occupancy, and conditional resampling can introduce conflicts. Thus after the first averaging step we must handle rules with small positive conflict probability, even though the original rule has zero conflict. Exact lists are no longer adequate: an event of tiny probability can make the set of possible outputs enormous. We use a short list together with the probability of falling outside it. Section 8 proves that a deleted part of mass τ and conflict probability w satisfies √ 2100 log D τ ≤ b + 6 w, b= . D √ Here mass means simply the probability of a nonzero output. w is able to bound τ thanks to the fact that for 0-round algorithms, conflict probability is quadratic in occupancy probability. Thus, taking the square roots makes the “units” agree. We prove this bound (Proposition 8.6) in three steps: 1. Upper-bounding edge-neighborhood tails by conflict probability (Proposition 8.2): This extends the one round argument from zero conflict to positive conflict rules. The main difference is that the notion of a shortlist is different: we upper bound the amount of mass outside of a shortlist (called a tail ) conditioned on a common edge-neighborhood (union of neighborhoods of endpoints). This once again uses the lack of large cliques in Erdős–Rényi graphs. 2. Upper-bounding vertex-neighborhood tails by edge-neighborhood tails (Lemma 8.5): Each edge-neighborhood tail corresponds to a short list of outputs, with different short lists for each of the branches. As in the one round argument, we have a bunch of independently-chosen short lists that must intersect. This once again guarantees a short merged list, but this time also provides a bound on the tail of that combined short list. 3a. Lower-bounding vertex-neighborhood tails by occupancy probability (Lemma 7.3): The expectation of a product of two vertex-neighborhood-derived tails is close to the product of expectations thanks to the near-independence of adjacent vertices. An entropy-based argument occurring in Section 7 that builds on Lemma 4.5 shows this. 3b. Upper-bounding conflict probability using occupancy probability: This uses Proposition 6.1, which in turn uses Lemma 4.5 to obtain the required similarity between the conditionally-resampled output distribution and the original one. Bounding losses: As rounds are eliminated, occupancy√probability tends to decrease, while conflict probability tends to increase. The loss estimate involves w. To sum losses, we need a bound on the sum of the deleted conflict probabilities. Section 9 first gives a direct, deliberately coarse calculation: charge the full possible information cost at each reduction. This gives a cubic term in r.

7

2.2.3

Ω̃(D1/2 )-Round Lower Bound

Next, we track the output entropy already created by earlier averaging steps. It cannot be charged anew at every step; it can disappear only when outputs are deleted. This gives a quadratic term via a telescoping sum. No other part of the argument changes. 2.2.4

The Main Ω(D/(log D))-Round Lower Bound

For the final argument, we only modify the third part of the prior arguments. Recall that the round elimination procedure takes the original r-round rule and repeatedly alternates between truncating and conditionally resampling to turn it into lower-radius rules. This can be replaced with a strategy that does all truncations first, followed by one combined conditional resampling step (Lemma 10.2). Qualitatively, this is more efficient as each truncated output is only truncated at one step and the loss can now be attributed only to that step as opposed to the multiple prior steps. Quantitatively, we get to use a more efficient multi-round analogue of Proposition 6.1 (Proposition 10.1) to replace Step (3b). This completes the proof of the occupancy theorem.

2.3

From the Occupancy Theorem to LOCAL

In the LOCAL model [10], vertices communicate synchronously along graph edges, with no restriction on message size or local computation. Every vertex runs the same program, has a distinct identifier and local port numbers, and may know n exactly. Private random tapes are independent between vertices; they may be infinite. We count a fixed worst-case number of communication rounds. Success means that the entire output is an MIS, rather than that each vertex is correct with a fixed probability. We allow degrees and neighbor identifiers to be known initially, which only strengthens the algorithms against which the lower bound holds. Theorem 1.2 concerns a rule whose only inputs are random inter-clique matrices. A LOCAL algorithm also sees identifiers and receives private randomness. We will turn it into a collection of edge-input rules without changing the matrix distribution. A Yao minimax-style argument gives the desired result. Preparing Vertex IDs Most of our task amounts to preparing the input to the LOCAL algorithm. First, we prepare vertex IDs. Each clique contains k vertices, and we must assign IDs to those vertices that are unique and different from IDs for vertices in any other clique. Note that a rule’s only access to randomness (i.e. symmetry-breaking) is through the skeleton edges. Thus, we extract vertex IDs from skeleton edges as follows. For simplicity, assume that k (the clique size) is even. Split the set of possible coordinate names [k] in each clique into two fixed halves {1, 2, . . . , k/2} and {k/2 + 1, . . . , k}. For a skeleton vertex v and a neighbor u, produce a bit string of length k 2 /4 by concatenating the (bit) entries Gvu (i, j) with i ≤ k/2 and j ≥ k/2 + 1 (i.e. first half rows to second half columns) in lexicographic order. Then, obtain a single length k 2 /4-bit string by XORing the strings for all neighbors of v. Note that this string does not require a port numbering to produce. Finally, break up this string into chunks with a fixed bID = Θ(log n) length and let the ith vertex in Cv receive the ith chunk as its identifier. Some chunks may go unused. For any pair of vertices u, v and any a ∈ Cu , b ∈ Cv , the IDs of a and b are independent random variables if a ̸= b thanks to the fact that the entries of Gvu from the first half rows to second half columns do not intersect with the entries of Gvu = GTuv from the second half rows to the first half columns. Thus, IDs are unique with high probability.4 Note though that IDs are correlated with the input graph, which is allowed. Preparing the Private Random Strings Note that we said that we would produce a collection of edge-input rules. We exploit this now. Fix a list of infinite bitstrings, with one bitstring for each of the 2bID possible vertex IDs. We will produce a 4 This argument assumes that IDs are only required to be at most nO(1) . A more nuanced argument is required when the IDs are required to be in [n]. This argument is described in the appendix.

8

separate edge-input rule for each possible list.5 We start by giving the vertex with ID i access to the ith bitstring in the fixed list. Obtaining a Collection of Zero-Conflict Edge-Input rules We now have unique vertex IDs for the vertices and tapes (bitstrings) for each vertex, so the supplied LOCAL algorithm may be applied. This results in one edge-input rule per list of bitstrings. The LOCAL algorithm produces a set of vertices in the input graph, though this set may not be an independent set thanks to the algorithm’s failure probability. We force the output set to be a (possibly not maximal) independent set by deleting any vertex from the output with a neighbor also in the output. This results in a collection of zero-conflict r + 3-round edge-input rules, where r is the round complexity of the LOCAL algorithm. Obtaining a Probability Contradiction Pick an arbitrary clique in the hard instance and apply each edge-input rule to that clique and let r = o((log n)/(log log n)). Then Theorem 1.2 says that the occupancy probability is subconstant for each rule. Taking the expectation over the collection implies that the expected occupancy probability is subconstant. By the probabilistic method, there exists a realization of the edges in the graph (and resultant vertex IDs) for which randomizing over tapes causes occupation of the chosen clique with subconstant probability. But this contradicts the fact that an MIS intersects each clique with high probability, the deletion postprocessing does not modify an MIS, and the LOCAL algorithm produces an MIS with constant probability for any input graph with unique IDs. This is the desired contradiction.

2.4

Outline and Reading Advice

Section 3 reduces Theorem 1.1 to Theorem 1.2, with some details deferred to the appendix. All other sections prove Theorem 1.2. Section 4 precisely defines r-round rules and proves the fundamental facts about entropy that are used throughout the paper. Section 5 proves a self-contained 1-round occupancy probability upper bound. Section 6 starts building towards round elimination by introducing the concept of conditional resampling. Section 7 proves near-independence of random variables on neighboring vertices in very general settings that are useful for reasoning about multiple round eliminations at a time. Section 8 proves the main round elimination bound (Proposition 8.6), effectively generalizing the techniques of Section 5. Section 9 proves the two weaker lower bounds, while Sections 10 and 11 complete the final result. The sections are ordered in terms of precedence: all later results only depend on earlier results, with the exception of the appendix. We recommend that the reader read the paper out-of-order. The reader should start with Section 3. Then, they should skim the results of Section 4, mostly to understand the definition of r-round rules. A reader who wants to focus on the high-level structure of the argument should skip ahead to Section 6, followed by the statement of Proposition 8.6. Then, read Section 9 and skim Section 10. At this point, the reader may understand the high-level structure of the argument and should return to Section 5. A reader who is more interested in techniques may prefer to start with Section 5 and then continue with the sections discussed for the high-level reader.

3

From the Occupancy Bound to Randomized LOCAL

Fix a T -round LOCAL algorithm A for n vertices. The algorithm may know n, use independent private random tapes, and see neighbor identifiers initially. We use legal port numbers obtained by sorting each vertex’s neighbors by identifier. Correctness on every legal input includes these port assignments. For w ∈ V (H), BtH (w) denotes the closed skeleton ball of radius t about w. Proposition 3.1 (Finite LOCAL obstruction). Let H be a simple D-regular graph on N vertices, with kN ≤ n and girth at least 2T + 8. Suppose D ≥ D0 , D ≤ log k ≤ D2 , k is even, and kbID ≤ ⌊k 2 /4⌋, 5 Note that there are uncountably many such lists, so the collection of obtained edge input rules is uncountable.

9

where bID = ⌈log2 n⌉. Set L=k 1+D

!

T +1 X

(D − 1)

i

,

δID =

i=0

L(L − 1) , n

γEXT = (k + 1)D exp(−k2−D ).

If A finds an MIS with probability at least σ > 0 on every legal n-vertex input, then   5000(T + 3) log D . σ(1 − δID − γEXT ) ≤ min 1, D

(2)

Proof. Replace every skeleton vertex by a k-clique, use independent fair edge matrices between neighboring cliques, and pad with isolated vertices to obtain exactly n vertices. Use Lemma A.1 to produce vertex IDs. This lemma works as follows. Partition clique coordinates into two parts P = {1, 2, . . . , k/2} and Q = {k/2 + 1, . . . , k − 1, k}. For the oriented edge v → u, assign the matrix block Gvu [P, Q] to v; the reverse direction uses the disjoint block Guv [P, Q] = (Gvu [Q, P ])T . XOR the assigned strings over all edges incident to v, and split the result into k strings of bID bits. Reducing each string modulo n and adding 1 gives tentative identifiers in [n]. They are mutually independent, with point probabilities at most 2/n, because different vertices use disjoint random bits. They can still be correlated with the graph. Independently sample one private tape Wi for every identifier i ∈ [n], and fix the entire table. Apply Lemma A.2 to this table to obtain a radius (T + 3)-rule. This works as follows. A vertex with tentative identifier i uses Wi . For every clique, simulate A only if all identifiers in its radius-(T + 1) skeleton ball are distinct; otherwise produce no candidates. Retain a candidate only when none of its graph neighbors is a candidate. This produces a deterministic, symmetric, always-independent edge-input rule of radius T + 3. Its occupancy at a fixed clique Cv is bounded by Theorem 1.2. The bound holds for every fixed tape table, so it also holds after averaging over that table. With probability at least 1 − δID , the tentative identifiers in BTH+2 (v) are all distinct. On this event, preserve these identifiers and complete them to a bijection on all n vertices. The completion depends on the matrices, not on the tapes. The candidates used to repair Cv agree with the outputs of A on this legal input. Distinct identifiers access distinct independent tapes, so the assumed success probability is at least σ on each such fixed input (Lemma A.3). Except on a graph event of probability at most γEXT , no choice of at most one vertex from each neighboring clique can dominate Cv . Thus every MIS occupies Cv (Lemma A.4). On the intersection of these two good graph events, a successful execution occupies Cv and survives conflict removal. Averaging first over the tapes and then over the matrices gives occupancy at least σ(1 − δID − γEXT ), proving (2). Proof of Theorem 1.1. Fix the success guarantee 0 < σ ≤ 1. For all sufficiently large n, suppose T < Choose

σ log n . 100000 log log n



 jnk log n D= , k = 2⌈eD /2⌉, N = 2 , g = 2T + 8. 4 2k Lemma A.5 supplies a D-regular graph on these N vertices with girth at least g: its sufficient size is 8Dg−2 , whereas N = n3/4+o(1) and Dg−2 ≤ n2σ/100000+o(1) . The remaining hypotheses of Proposition 3.1 hold for large n (Lemma A.6). Moreover, δID ≤

(2kDT +2 )2 ≤ n−1/2+2σ/100000+o(1) = o(1), n

and log γEXT ≤ D(D + 1) − e(1−log 2)D −→ −∞. Its left-hand side is therefore σ − o(1). Since D ≥ (log n)/5 and log D ≤ log log n for large n, its right-hand side is at most σ/4 + o(1), a contradiction. All thresholds depend only on σ and the absolute occupancy constants, not on the algorithm. This proves the claimed worst-case lower bound, including algorithms that know n and use the identifier space [n]. For σ = 2/3, the same estimates with T < log n/(100000 log log n) give 2/3 − o(1) on the left and 1/4 + o(1) on the right, establishing the stated special constant. 10

4

Preliminaries

The rest of the paper proves Theorem 1.2. In this section, we discuss relevant definitions.

4.1

Radius-s Rules

For a skeleton vertex v, let Es (v) contain the edges with both endpoints in the closed radius-s ball around v. Write Ns (v) for the tuple of matrices on these edges. The underlying rooted tree is fixed; all randomness in a view comes from the matrices. In particular, N0 (v) is empty. For conditioning, we name the positions of these independent variables on a fixed tree. These names are bookkeeping for the proof and are not inputs to a rule. Symmetric local selection rule. A radius-s rule A assigns to every view y = Ns (v) numbers π0 (y), π1 (y), . . . , πk (y) ≥ 0 with sum 1. At v it outputs a ∈ {0, . . . , k} with probability πa (y). Conditional on all matrices, these output draws are independent at different vertices. The assignment is the same at every skeleton vertex and is unchanged by rooted isomorphisms of the matrix-labeled tree that preserve clique-coordinate names. This is the symmetry assumption. A deterministic rule assigns probability 1 to one output. An independent-set rule has ϵ(A) = 0. We use ordinary finite conditional probabilities throughout. For example, P[Z = a | Y = y] is the probability of output a after fixing the input information Y to be y. The conditional distribution is the list of these probabilities for all a; it is sometimes called a conditional law. We will write the probabilities explicitly when constructing a new rule. The support of a distribution is the set of outputs having positive probability. Shared information and probability outside a list.

For adjacent u, v and t ≥ 0, put

Ft (uv) = {Guv } ∪ Nt (u) ∪ Nt (v), where the union retains each matrix variable once. For a random output Z ∈ {0} ∪ [k], define taila (Z | Y = y) = min P[Z ∈ / S ∪ {0} | Y = y]. S⊆[k] |S|≤a

Without Y this denotes the unconditional probability. The minimizing list consists of the a most probable nonzero coordinates, or all coordinates when a ≥ k. Ties are always broken by coordinate order. We also write taila (P ) when P is a specified probability distribution. The number taila measures the probability missed by the best a-coordinate list. Output 0 is included for free; it is never a selected graph vertex. We repeatedly use the following lemma, which uses the skeleton graph’s high girth: Lemma 4.1 (Product decomposition of local views). Let s ≥ 1. At an edge uv, the shared view F = Fs−1 (uv) contains the central matrix and both Ns−1 (u) and Ns−1 (v). Conditional on F , the remaining data in Ns (u) and Ns (v) are independent. Consequently, the outputs of any radius-s rule at u, v are independent conditional on F . At a root v, enumerate its neighbors as v1 , . . . , vD only for analysis, and put Y = Ns−1 (v). Let Xi be the matrix data in Fs−1 (vvi ) outside Y . Conditional on Y , the Xi are independent, their union supplies exactly the data in Ns (v) outside Y , and Fs−1 (vvi ) is specified by (Y, Xi ). Proof. On a tree, the shared edge set is Es (u) ∩ Es (v) = {uv} ∪ Es−1 (u) ∪ Es−1 (v). The two edge sets outside this intersection are disjoint. All edge matrices are independent, so conditioning on the shared matrices leaves these two collections independent. The independent private output draws preserve this conditional independence. For the second assertion, the edges of Ns (v) outside Y are the edges between depths s − 1 and s. They partition according to the first neighbor on the path from v. The part in branch i is exactly Xi , including the central edge vvi when s = 1. These parts are disjoint and independent of the inner edge data. This proves every assertion.

11

other inputs at u

other inputs at v Guv u

v

Fix the orange matrix. The blue and red inputs remain independent.

Figure 1: The shared information for two one-round views, shown for D = 3. Every circle denotes an entire clique, and every line denotes its random bipartite matrix. At general radius, fixing Fs−1 (uv) leaves the two remaining input regions independent in the same way.

4.2

Entropy

For a finite random variable Z with probabilities pz , define X X H(Z) = pz log(1/pz ), H(Z | Y ) = P[Y = y]H(Z | Y = y). y

z:pz >0

All logarithms are natural in this paper unless otherwise mentioned. An output with m equally likely possibilities has entropy log m; an output determined by the available information has conditional entropy zero. Write h(x) = −x log x − (1 − x) log(1 − x) for binary entropy, using 0 log 0 = 0. Define I(Z; X | Y ) = H(Z | Y ) − H(Z | X, Y ). This conditional mutual information is the amount by which seeing X reduces the uncertainty in Z, once Y is known. For probability distributions P, Q on the same finite set, their relative entropy is KL(P ∥Q) =

X x:P (x)>0

P (x) log

P (x) . Q(x)

It is +∞ if Q(x) = 0 < P (x) for some x. The inequality log z ≤ z − 1 shows KL(P ∥Q) ≥ 0. Expanding definitions gives the entropy chain rule H(X, Z | Y ) = H(X | Y ) + H(Z | X, Y ). It also expresses I(Z; X | Y ) as the average relative entropy of the conditional joint distribution from the product of its conditional marginals. Thus I ≥ 0, or equivalently, conditioning cannot increase entropy. Comparing a distribution on at most m values with the uniform distribution gives H ≤ log m. These facts also give subadditivity and the chain rule for I. Lemma 4.2 (Square-root event probabilities). For probability distributions P, Q on a finite set and any event E, !1/2 p p | P (E) − Q(E)| ≤

Xp p ( P (x) − Q(x))2

≤

p

KL(P ∥Q).

(3)

x

Proof. The first inequality is the reverse triangle inequality for the square-root vectors restricted to E, followed by enlargingPthepsum to all x. If the relative entropy is infinite there is nothing more to prove. Otherwise, put a = x P (x)Q(x). Jensen’s inequality for the logarithm gives s Q(x) 1 log a = log E ≥ − KL(P ∥Q). P (x) 2 x∼P Thus KL(P ∥Q) ≥ −2 log a ≥ 2(1 − a). The squared middle expression in (3) equals 2(1 − a).

12

We use square roots because the baseline conflict probability will be quadratic in occupancy. This inequality converts a relative-entropy bound directly into a bound on that scale. We bound KL-divergence using the following conditional resampling-oriented result that shifts randomness from the outer rim determining A to the middle, leaving a lower-radius neighborhood YA : Lemma 4.3 (Relative entropy of conditional resampling). Let F, A, B be finitely-supported random variables, and let YA , YB be functions of F . Let P be the distribution of (F, A, B). Define Q by keeping the same distribution of F and, conditional on F = f , drawing the two outputs independently with probabilities P[A = a | YA = YA (f )], P[B = b | YB = YB (f )]. Then

KL(P ∥Q) = H(A | YA ) + H(B | YB ) − H(A, B | F ) = I(A; F | YA ) + I(B; F | YB ) + I(A; B | F ).

In particular, if A, B are independent conditional on F , then KL(P ∥Q) = I(A; F | YA ) + I(B; F | YB ). This conditional independence holds whenever A = α(F, U ) and B = β(F, V ) for random variables U, V that are independent conditional on F . Proof. Write pf (a, b) = P[A = a, B = b | F = f ], qA (a | y) = P[A = a | YA = y], and similarly for qB . The finite support makes it so that these probabilities are discrete rather than density functions. If P (f, a, b) > 0, then both qA (a | YA (f )) and qB (b | YB (f )) are positive. Thus the likelihood ratio is defined on the support of P . The common probability of F = f cancels, giving KL(P ∥Q) = E[log pF (A, B) − log qA (A | YA ) − log qB (B | YB )] . P

The three terms are −H(A, B | F ), H(A | YA ), and H(B | YB ). This proves the first identity. Since YA , YB are functions of F , I(A; F | YA ) = H(A | YA ) − H(A | F ),

I(B; F | YB ) = H(B | YB ) − H(B | F ).

Together with I(A; B | F ) = H(A | F ) + H(B | F ) − H(A, B | F ), these equalities prove the second identity. Conditional independence gives I(A; B | F ) = 0. Finally, functions of conditionally independent inputs remain conditionally independent. Next, we bound the entropy of a distribution whose probability mass is both very lopsided and supported on a small number of outputs: Lemma 4.4 (Entropy of a rarely nonzero output). Suppose the conditional distribution of C ∈ {0} ∪ [k] given Y is supported on at most m nonzero labels and 0, for an integer m ≥ 1. If p = P[C ̸= 0], then H(C | Y ) ≤ h(p) + p log m ≤ p log(em/p),

(4)

where h(p) = −p log p − (1 − p) log(1 − p) and the last expression is defined as 0 at p = 0. Also x 7→ x log(em/x) is increasing on [0, 1]. Proof. Let J = 1{C̸=0} . The chain rule gives H(C | Y ) = H(J | Y ) + H(C | J, Y ) ≤ h(p) + p log m. Here H(J | Y ) ≤ H(J) = h(p) and, given J = 1, Y , at most m labels remain. The inequality −(1 − p) log(1 − p) ≤ p gives the second bound. Finally the derivative of x log(em/x) is log(m/x) ≥ 0 for 0 < x ≤ 1. The factor p in this last estimate matters: uncertainty about a coordinate is incurred only when an output is nonzero. We will preserve this factor in the final accounting.

13

Lemma 4.5 (Independent inputs share an information budget). If X1 , . . . , XD are independent conditional on Y , then for any finite random variable Z, D X

I(Z; Xi | Y ) ≤ I(Z; X1 , . . . , XD | Y ) = H(Z | Y ) − H(Z | Y, X1 , . . . , XD ).

i=1

Additional private randomness in Z is allowed. Proof. Let X<i = (X1 , . . . , Xi−1 ). Independence gives H(Xi | Y, X<i ) = H(Xi | Y ), while conditioning gives H(Xi | Z, Y, X<i ) ≤ H(Xi | Z, Y ). Subtract to obtain I(Z; Xi | Y, X<i ) ≥ I(Z; Xi | Y ). Sum and apply the chain rule.

4.3

Table of Parameters and Constants

Table 1 records the parameters and numerical constants used in Sections 4–11. These choices are deliberately loose. The threshold D0 is one absolute constant large enough for all the stated parameter inequalities; it is independent of the radius r and of the selection rule. All logarithms in this table and in the occupancy proof are natural. Table 1: Parameters and numerical constants used in the occupancy proof. Parameter or constant Choice and purpose Main parameters and list sizes D, k, r, D0 Skeleton degree, clique size, view radius, and absolute degree threshold; D ≥ D0 , D ≤ log k ≤ D2 , r ≥ 1. ℓ ⌈100 log(k + 1)⌉: size of a list supplied by one shared edge view. M ⌈1000ℓ⌉: size of the list consolidating independent branch lists; M ≤ D3 . m DM : number of nonzero coordinates retained before resampling; m ≤ D4 . q Exceptional-matrix probability; 2 q ≤ e−ℓ /10 ≤ D−2 . η 1/D = M/m: an upper bound on the deleted mass captured by an M -coordinate list. δ 256 log D/D: bound on the fraction of branches offering an unusually good short list. b 2100 log D/D: additive occupancy loss in one truncation.

5

Use or derivation Theorem 1.2.

Lemma 5.1; (7). (7). (7). Lemma 5.1. (13). Lemmas 8.4 and 8.5. Proposition 8.6.

Warmup: One-Round Hardness

This section proves that a one-round independent-set rule cannot occupy a constant fraction of cliques as D grows. The proof has two steps: put almost all outputs in a fixed short list, then show that an independent-set rule restricted to that list rarely selects anything.

5.1

1-Round Algorithms have Short Output Lists

We begin with two key facts. The first rules out large rectangles of compatible choices. We prove a density statement because its quantitative form will also be useful when conflicts have small positive probability. Lemma 5.1 (Almost-empty random submatrices). Let G be a k-by-k matrix of independent Bernoulli1/2 entries and let ℓ = ⌈100 log(k + 1)⌉ ≤ k. Call G exceptional if it contains an ℓ-by-ℓ submatrix with at most ℓ2 /4 entries equal to 1. Then 2

2

q := P[G is exceptional] ≤ k 2ℓ e−ℓ /8 ≤ e−ℓ /10 . 14

(5)

Proof. For N independent Bernoulli-1/2 variables Bj ,   N X 2 (Bj − 1/2) = cosh(λ/2)N ≤ eN λ /8 . E exp −λ j=1

The last inequality follows from log cosh x ≤ x2 /2; its derivative inequality P is tanh x ≤ x for x ≥ 0, and both functions are even. Taking λ = 1 in Markov’s inequality yields P[ j Bj ≤ N/4] ≤ e−N/8 . Apply this with N = ℓ2 to a fixed submatrix and take a union bound over at most k 2ℓ choices of its rows and columns. Since log k ≤ ℓ/100, the resulting exponent is at most −ℓ2 (1/8 − 2/100) ≤ −ℓ2 /10. The second fact explains how many independent, varying lists can force membership in one fixed list. A label’s weight is its expected number of occurrences among the random lists. Only a few labels can have large weight because each list is short. Independence makes it unlikely that a small-weight label nevertheless appears many times. Lemma 5.2 (Frequently occurring labels . . , SD be independent random P lie in a fixed list).PLet S1 , . P subsets of [k]. 6 For a ∈ [k], put wa = i P[a ∈ Si ] and C = a wa = i E |Si |. Let B consist of the M labels of largest wa , with ties broken by coordinate order; if M ≥ k, let B = [k]. For any integers M ≥ 1 and h ≥ 2, / B belongs to at least h of the Si ] ≤ P[some a ∈

(eC/h)h . (h − 1)M h−1

(6)

P Proof. For a fixed a, the membership indicators in the D lists are independent. If Na = i 1{a∈Si } , then    ew h Na wh a ≤ a ≤ . P[Na ≥ h] ≤ E h! h h The middle inequality expands the factorial moment as a sum over distinct indices and compares it to the full expansion of wah . Order the weights decreasingly as w(1) , . . . , w(k) . Since w(j) ≤ C/j, a union bound gives  h X (eC/h)h eC j −h ≤ , / B : Na ≥ h] ≤ P[∃a ∈ h (h − 1)M h−1 j>M

where the sum is bounded by the integral over [M, ∞). We will repeatedly use the following elementary concentration bound, with its proof included to fix the constants. Lemma 5.3 (Too few eligible branches). Let L be a sum of independent indicator variables, with ν = E L. For 0 < a ≤ 1, −a2 ν/2 . P[L < (1 − a)ν] ≤ e Proof. If the indicators have success probabilities pi , then Y −λL = (1 + pi (e−λ − 1)) ≤ exp(ν(e−λ − 1)). Ee i

Apply Markov’s inequality and use e bound.

−λ

≤ 1 − λ + λ2 /2 for λ ≥ 0. Choosing λ = a gives the displayed

Use the following list sizes for the remainder of the proof: ℓ = ⌈100 log(k + 1)⌉,

M = ⌈1000ℓ⌉,

m = DM.

(7)

Uniformly for D ≤ log k ≤ D2 , and sufficiently large D, ℓ ≤ k,

M ≤ D3 ,

m ≤ D4 ,

2

q ≤ e−ℓ /10 ≤ D−2 ,

where q is the exceptional-matrix probability. Indeed ℓ = O(D2 ), M = O(D2 ), m = O(D3 ), and k ≥ eD . Every threshold here is independent of the rule. 6 The distribution that each S

i is sampled from need not be uniform.

15

Proposition 5.4 (A fixed list for a one-round independent-set rule). Let A be a symmetric radius-one rule with ϵ(A) = 0. There is a fixed set B ⊆ [k], |B| ≤ M , such that / B ∪ {0}] ≤ D−2 P[Av ∈ for all sufficiently large D in the parameter regime above. Proof. For a fixed central matrix g, define Su (g) = {a ∈ [k] : P[Au = a | Guv = g] > 0}, and define Sv (g) similarly, using the endpoint orientation. Conditional on g, the outputs are independent by Lemma 4.1. Their conditional conflict probability is zero: it is nonnegative and its expectation is ϵ(A) = 0. Thus g(a, b) = 0 for every a ∈ Su (g), b ∈ Sv (g). For a nonexceptional g, both sets cannot have size at least ℓ. It follows that 1{|Su (Guv )|<ℓ} + 1{|Sv (Guv )|<ℓ} ≥ 1 unless Guv is exceptional. Endpoint symmetry gives P[|Su (Guv )| < ℓ] ≥ (1 − q)/2. At a root v, write Xi = Gvvi for its D independent incident matrices. Call branch i eligible when the conditional nonzero support of Av given Xi has size less than ℓ. Let Si be that support on eligible values and the empty set otherwise. Each list depends only on Xi , so the lists and the eligibility indicators are independent across i. If L counts eligible branches, then ν = E L ≥ D(1 − q)/2 ≥ D/3 for large D. Whenever Av ̸= 0, it belongs to every eligible list, with probability one. Lemma 5.3 gives P[L < D/6] ≤ e−D/24 . Set h = ⌊D/6⌋ ≥ D/7 for large D. The total list weight is at most Dℓ. Let B be the M coordinates of largest weight. Since eDℓ/(hM ) ≤ 7e/1000 < 1/2, Lemma 5.2 gives M −h / B : a occurs in at least h lists] ≤ 2 . P[∃a ∈ h−1 If the output is nonzero and outside B, then either L < D/6 or this last event occurs. Therefore its probability is at most M −h e−D/24 + 2 ≤ D−2 h−1 eventually, because M ≤ D3 and h ≥ D/7.

5.2

Short Lists Imply Low Occupancy

We now turn a list-size bound into an occupancy bound. This is the first use of hiding input information and resampling. Here we hide all the input, so the new rule simply uses fixed output probabilities. Lemma 5.5 (Forgetting a one-round view). Let C be a symmetric radius-one independent-set rule whose nonzero outputs lie in a fixed set of size at most M . Write z = p(C), and let Q draw independently at each vertex from the unconditional probabilities of Cv . Then z2 2H(Cv ) 2z eM = ϵ(Q) ≤ ≤ log . 2 D D z Proof. At v, the D incident matrices Xi are independent. Lemma 4.5 and branch symmetry give I(Cv ; Xi ) ≤ H(Cv )/D for a specified i. Let P be the actual distribution of (Guv , Cu , Cv ). Note that Guv is one of the Xi s. Let Q have the same matrix distribution and independent outputs with the unconditional probabilities of C. Lemma 4.3 and the conditional independence of the old outputs given Guv give KL(P ∥Q) = 2H(Cv ) − H(Cu , Cv | Guv )
2H(Cv ) . = 2 H(Cv ) − H(Cv | Guv ) ≤ D The conflict event has probability zero under P . Under Q, both outputs are nonzero with probability z 2 , and their selected matrix entry is an independent fair bit. Thus it has probability z 2 /2. Apply Lemma 4.2 and square, then use Lemma 4.4. 16

Proposition 5.6 (One-round occupancy bound). For sufficiently large D, uniformly for D ≤ log k ≤ D2 , every symmetric radius-one rule A with zero conflict has p(A) ≤

25 log D . D

Proof. Use the fixed list B from Proposition 5.4. Let Cv = Av when Av ∈ B, and let it be zero otherwise. This only deletes selections, so ϵ(C) = 0. Its occupancy z satisfies p(A) ≤ z + D−2 . If z < 1/D, the conclusion follows immediately. Otherwise Lemma 5.5, divided by z > 0, gives z≤

4 eM 4(1 + 4 log D) 20 log D log ≤ ≤ , D z D D

where M ≤ D3 , z ≥ 1/D, and log D ≥ 1. Adding D−2 proves the stated bound. The proof explains why the graph’s random matrices do not give the algorithm unlimited freedom to choose different coordinates. Independence constrains the possible outputs in many separate branches, and the information budget constrains coordination even after those outputs are confined to one short list. For larger radii, adjacent smaller views overlap and the intermediate rules can have positive conflict probability. We now extend the two parts of the warmup to address these two issues, while keeping track of their quantitative costs.

6

Round Elimination by Conditional Resampling

Suppose a radius-s output Zv depends on an inner view Y = Ns−1 (v) and an outer input layer. For every possible inner view y, compute the probabilities qa (y) = P[Zv = a | Y = y]

(a = 0, . . . , k).

These probabilities average over the hidden matrices and any private randomness of the old rule. A new radius-(s − 1) rule can output a with probability qa (y). It does not need to see, or reconstruct, the actual outer layer. We call this operation conditional resampling. The proof allows arbitrary computation, so these finite probabilities define a legitimate rule. Conditional resampling preserves the probability of every output at a single vertex after averaging over all inputs. It can change how outputs at neighboring vertices depend on each other and on the central matrix. That change is exactly what must be bounded. Proposition 6.1 (The information cost of removing one round). Let Z be a symmetric radius-s rule, s ≥ 1. Let Q be its conditional resampling onto Ns−1 (v). Put d = H(Zv | Ns−1 (v)) − H(Zv | Ns (v)). Then d ≥ 0, p(Q) = p(Z), and p

ϵ(Q) ≤

p

ϵ(Z) +

p 2d/D.

(8)

Proof. Nonnegativity follows because conditioning decreases entropy, and occupancy is preserved by averaging conditional probabilities. Write Y = Ns−1 (v) and use the independent branch extensions X1 , . . . , XD from Lemma 4.1. Their union with Y is Ns (v), so Lemma 4.5 gives X I(Zv ; Xi | Y ) ≤ d. i

After averaging over Y , all D terms are equal by symmetry. For a specified incident edge, its shared information is F = (Y, Xi ), and hence H(Zv | Y ) − H(Zv | F ) ≤ d/D. We do not assert equality between branches after fixing one particular inner view; the equality is in the averaged entropies. 17

Let P be the actual joint distribution of (F, Zu , Zv ). Let Q keep the same F distribution and independently draw the two outputs from their respective smaller-view probabilities. This is the distribution generated by Q at the edge. The old outputs are independent conditional on F by Lemma 4.1. Lemma 4.3 gives KL(P ∥Q) = 2H(Zv | Ns−1 (v)) − H(Zu , Zv | F )
= 2 H(Zv | Ns−1 (v)) − H(Zv | F ) ≤ 2d/D. The tuple F contains the central matrix, so conflict is the same event in the two probability spaces. Apply Lemma 4.2 to obtain the desired result. The quantity H(Zv | Ns (v)) is the uncertainty left in the private output draw when all of the old input is known. The number d is the additional uncertainty caused by hiding one layer. This interpretation will matter when we sum the costs of successive reductions. It would not help to apply this operation immediately to a rule that might output any of the k coordinates: its entropy could be as large as log(k + 1), which is too large in our regime. As in the warmup, we first restrict outputs to a much shorter list. At larger radii that list depends on the inner view. To control the mass lost this way, we next need an estimate on how strongly two neighboring inner views can coordinate their deleted masses.

7

Multi-Round Entropy Bounds

The independent-input calculation in the warmup is especially simple because the root sees one independent matrix per branch. At higher radius, the smaller views of adjacent vertices overlap. We need a bound that respects this overlap. The principle is that local outputs cannot share too much information compared with their individual uncertainty. We prove a conditional version, so that already known matrices are accounted for exactly.

7.1

Single-Layer Bounds

We compare the entropy revealed by one additional layer at a vertex with the entropy revealed by that layer at an edge. The independent-input information budget applies twice: first to the D branches at a vertex, then to the two independent completions of a shared edge view. Lemma 7.1 (One-layer conditional entropy increment). Let Z be a symmetric radius-R rule. For adjacent u, v, put Hh = H(Zv | Nh (v)),

Jh = H(Zu , Zv | Fh (uv)),

0 ≤ h ≤ R.

For every 0 ≤ h < R, Jh − Jh+1 ≥

2(D − 1) (Hh − Hh+1 ). D

Proof. Fix h < R and write ∆h = Hh − Hh+1 . At v, put Y = Nh (v) and enumerate its neighbors as v1 , . . . , vD for analysis, with v1 = u. Let Xi be the matrix data in Fh (vvi ) outside Y . Lemma 4.1, applied with s = h + 1, says that the Xi are independent conditional on Y , their union completes Nh+1 (v), and Fh (vvi ) is specified by (Y, Xi ). Lemma 4.5 therefore gives D X

I(Zv ; Xi | Y ) ≤ I(Zv ; X1 , . . . , XD | Y ) = ∆h .

i=1

The D terms are equal by branch symmetry after averaging over Y . Consequently I(Zv ; X1 | Y ) ≤ ∆h /D. Write F = Fh (uv) and A = (X2 , . . . , XD ). Since F is specified by (Y, X1 ), the chain rule gives I(Zv ; A | F ) = ∆h − I(Zv ; X1 | Y ) ≥

18

D−1 ∆h . D

Define B in the same way at u, using all branches except the one toward v. The corresponding inequality is D−1 I(Zu ; B | F ) ≥ ∆h . D The same ∆h applies at both endpoints by symmetry. The tuples A and B contain exactly the matrix data in Nh+1 (v) and Nh+1 (u), respectively, outside F . By Lemma 4.1, these are disjoint independent completions conditional on F , and together they complete Fh+1 (uv). Apply Lemma 4.5 to these two inputs and the joint output to obtain Jh − Jh+1 = I((Zu , Zv ); A, B | F ) ≥ I((Zu , Zv ); A | F ) + I((Zu , Zv ); B | F ) ≥ I(Zv ; A | F ) + I(Zu ; B | F ) ≥

2(D − 1) ∆h . D

The second inequality retains one component of the joint output in each mutual information term. The outputs themselves need not be independent conditional on F .

7.2

Multiple Layers via Telescoping

The one-layer comparison telescopes over all hidden layers. At the complete input view, only the independent private output draws remain uncertain. Lemma 7.2 (Conditional edge entropy). Let Z be a symmetric radius-R rule, and let 0 ≤ t ≤ R. At adjacent u, v, use Ft = {Guv } ∪ Nt (u) ∪ Nt (v). With K = H(Zv | NR (v)), we have D H(Zu , Zv | Ft ) ≥ (D − 1)H(Zv | Nt (v)) + K. 2

(9)

Proof. Use Hh , Jh from Lemma 7.1. Summing its inequality for h = t, . . . , R − 1 gives Jt − JR ≥

2(D − 1) (Ht − HR ). D

When t = R, the sum is empty and both differences are zero. By definition HR = K. The shared view FR determines the complete input views of both outputs. Conditional on FR , their private draws are independent, and the conditional distribution of each output depends only on its own NR view. Hence JR = H(Zu | FR ) + H(Zv | FR ) = 2K. Substitute these identities into the telescoped inequality: Jt ≥ 2K +

2(D − 1) 2 2(D − 1) (Ht − K) = Ht + K. D D D

Multiplying by D/2 proves the claim. The estimate concerns conditional entropy of the outputs, so it does not include the entropy of the surrounding raw matrices. Its bound has no factor for the number of hidden layers because the entropy increments telescope. All conditional entropies and mutual informations above are averaged over their conditioning variables. The input independence used in the proof is conditional on raw views, not on an output or on a selection event.

7.3

Implications for Local Probabilities

The next application turns an arbitrary local number in [0, 1] into the success probability of a private coin. This lets the entropy inequality control how rarely large values can meet across an edge.

19

Lemma 7.3 (Entropy bound for scalar coincidences). Let fv be the same symmetric finite-radius function of the edge inputs at every vertex, with 0 ≤ fv ≤ 1 and µ = E fv . For adjacent u, v, E[fu fv ] ≥

µ2 2h(µ) − . 2 D

(10)

Proof. Independently at each vertex conditional on the matrices, sample Bv ∈ {0, 1} with success probability fv . Then P[Bv = 1] = µ and e := P[Bu = Bv = 1] = E[fu fv ]. Lemma 7.2 with t = 0 implies

7

H(Bu , Bv ) ≥ H(Bu , Bv | Guv ) ≥ 2(1 − 1/D)h(µ). Thus I(Bu ; Bv ) ≤ 2h(µ)/D. Compare their joint distribution P (with P (i) being the marginal for i) with the product of their marginals Q(i, j) = P (i)P (j): KL(P ∥Q) =

1 X 1 X

P (i, j) log(P (i, j)/Q(i, j)) = 2

i=0 j=0

1 X

P (i) log(1/P (i)) − H(P ) = I(Bu ; Bv )

i=0

p √ Thus, for the event that both variables equal 1, Lemma 4.2 gives | e − µ| ≤ 2h(µ)/D. Hence µ2 ≤ 2e + 4h(µ)/D, proving the assertion. The error term is h(µ)/D, which is small when the mean µ is small. This dependence on the mean is important when the number fv represents a small probability of deletion.

8

Obtaining Shortlists via Round Elimination

In the one-round warmup, zero conflict forced one endpoint’s conditional support to be short. An intermediate rule obtained by resampling can have positive conflict probability, and then that exact conclusion need not hold. We need a statement about the probability outside short lists. We develop its matrix, branch, and neighboring-vertex parts in that order.

8.1

Conflict Probability Bounds Edge Tails

For a typical central matrix, two independent output distributions cannot both place substantial probability outside every ℓ-coordinate list without creating conflicts. The following lemma remains valid when the two distributions were themselves chosen after seeing the matrix. Lemma 8.1 (Two diffuse distributions across one matrix). Let G be a nonexceptional matrix as in Lemma 5.1, and let P, Q be arbitrary distributions on {0} ∪ [k]. If A ∼ P and B ∼ Q independently and e = P[A, B ̸= 0, G(A, B) = 1], then tailℓ (P ) tailℓ (Q) ≤ 4e.

(11)

The distributions may depend arbitrarily on G. Proof. Put a = tailℓ (P ) and b = tailℓ (Q). If either is zero the conclusion holds. Otherwise sample ℓ distinct nonzero labels A1 , . . . , Aℓ by drawing sequentially from P , conditioning each draw to avoid 0 and all previous labels. At every stage, the conditioning event has P -probability at least a. Therefore, for every stage i and every label x, P[Ai = x] ≤ P (x)/a. Independently perform the corresponding procedure for Q to obtain B1 , . . . , Bℓ , with P[Bj = y] ≤ Q(y)/b. For every i, j, independence between the two procedures gives 1 X e P (x)Q(y)G(x, y) = . E[G(Ai , Bj )] ≤ ab ab x,y∈[k]

If e < ab/4, the expected edge density of the sampled submatrix would be less than 1/4, so some such submatrix would have density less than 1/4. This contradicts nonexceptionality. 7 This uses the fact that B is a rule in an unexpected way; i.e. that it only is allowed to output 0 or 1.

20

Proposition 8.2 (Conditional endpoint tails). Let C be a symmetric radius-s output rule, with s ≥ 1. For an edge uv let F = Fs−1 (uv) and define zu (F ) = tailℓ (Cu | F ),

zv (F ) = tailℓ (Cv | F ),

where ℓ and q are as in Lemma 5.1. Then E[zu (F )zv (F )] ≤ 4ϵ(C) + q.

(12)

Proof. By Lemma 4.1, the endpoint outputs are independent conditional on F , and the central matrix is known from F . For a nonexceptional central matrix, Lemma 8.1 bounds zu zv by four times the conditional conflict probability. On the exceptional event use zu zv ≤ 1. Average over F to obtain the claim. In particular, no independence between the conditional output distributions and the central matrix is being assumed.

8.2

Edge Tails Bound Vertex Tails

We next generalize the independent-list argument from the warmup. An eligible branch8 now provides a list that captures the output with probability at least 1 − t/2, rather than with probability one. The capture events at different branches need not be independent, because they concern the same output. Only the eligibility indicators and the lists themselves are independent across branches. Lemma 8.3 (Many eligible lists capture the output together). Let X1 , . . . , XD be independent finite random variables. For each i, let Li be an event determined by Xi , and let Ci be an event on the full probability space. Suppose 0 < t ≤ 1 and P P[Ci | Xi = x] ≥ 1 − t/2 for every eligible value x (that is, every x for which Li occurs). Put ν = i P[Li ]. If e−ν/128 ≤ t/12, then " # X 1Li ∩Ci ≥ ν/8 ≥ 1 − 3t/4. P i

Proof. Let L count eligible branches, let T count eligible branches whose capture event holds, and put U = L − T . The hypothesis gives E[U ] ≤ tν/2. Since the eligibility indicators are independent, Lemma 5.3 with a = 1/8 gives P[L < 7ν/8] ≤ e−ν/128 . On {T < ν/8, L ≥ 7ν/8} we have U ≥ 3ν/4. Markov’s inequality therefore yields P[T < ν/8] ≤

2t t 3t E[U ] + e−ν/128 ≤ + = . 3ν/4 3 12 4

The occurrence threshold is a constant fraction ν/8, even when t is small. The small value of t is used to bound the probability that so many capture events fail. Lemma 8.4 (Parameter bounds for branch consolidation). Use ℓ, M, m from (7), and set η=

1 , D

δ=

256 log D . D

(13)

For sufficiently large D, uniformly for D ≤ log k ≤ D2 , we have M/m = η, m ≤ D4 , δ < 1, q ≤ D−2 , and, for every integer h ≥ 32 log D − 1, h ≥ 2,

M −h 1 2 < . h−1 8D

Proof. The size and matrix bounds were verified after (7). The ratio M/m is exact and 256 log D/D < 1 eventually. For the last inequality, use M ≤ D3 and monotonicity in h: M −h D3 2−(32 log D−1) 2 ≤ = o(D−1 ). h−1 32 log D − 2 All thresholds depend only on absolute constants. 8 Recall that a branch is an incident edge-neighborhood to the root.

21

The next lemma says that if every fixed M -coordinate list leaves probability at least t outside, then only a small fraction of branches can offer an ℓ-coordinate list with the substantially smaller error t/2. Lemma 8.5 (Relative branch transfer with a uniform exception bound). Use the parameters of Lemma 8.4. Let X1 , . . . , XD be independent finite random variables, and let Z ∈ {0} ∪ [k] have any conditional distribution given them. Put t = tailM (Z). If t ≥ 1/D, then, for an independent uniform I ∈ [D], (14) P [tailℓ (Z | I, XI ) < t/2] ≤ δ. I,XI

The assertion also holds conditional on any fixed inner view under which the branch extensions are independent. Proof. Suppose the displayed probability exceeds δ. Call a value of Xi eligible when its conditional ℓ-tail is less than t/2. Choose a minimizing ℓ-label list there, and use the empty list otherwise. The resulting random lists Si are independent. The mean eligible count satisfies ν > δD = 256 log D. At eligible values the capture event Z ∈ Si ∪ {0} has conditional probability greater than 1 − t/2. For sufficiently large D, e−ν/128 < D−2 ≤ t/12. Lemma 8.3 gives simultaneous capture in at least ν/8 eligible lists with probability at least 1 − 3t/4. Set h = ⌊ν/8⌋. Then h ≥ 32 log D − 1 and h ≥ ν/16. The total list weight in Lemma 5.2 is C ≤ ℓν, so eC/(hM ) ≤ 16e/1000 < 1/2. The M labels of largest weight form a fixed list B. By Lemmas 5.2 and 8.4, the probability that some label outside B occurs in at least h lists is less than 1/(8D) ≤ t/8. Thus P[Z ∈ B ∪ {0}] > 1 − 3t/4 − t/8 = 1 − 7t/8 > 1 − t, contradicting the definition of t. For a fixed inner view, apply the same argument to the conditional product distribution. It uses no identical-distribution assumption.

8.3

Sandwiching Vertex Tails between Occupancy and Conflict via Entropy

Fix a radius-s rule and a smaller view Y = Ns−1 (v). Retain its m most probable nonzero coordinates given Y . The kept rule returns the original coordinate when it belongs to this list and returns 0 otherwise. The deleted rule returns the original coordinate exactly when it is nonzero and outside this list. They partition the original nonzero outputs at each vertex. Why should the deleted mass be small? Every deleted coordinate has conditional probability at most 1/m, so a much shorter list of M = m/D coordinates can capture at most 1/D of that mass. The branch lemma (Lemma 8.5) says that this spread in the smaller view usually persists in the shared edge view. The endpoint-tails proposition (Proposition 8.2) then forces a conflict when it persists at both endpoints. The scalar entropy estimate (Lemma 7.3) ensures that the large deleted masses cannot avoid meeting too often. Proposition 8.6 (Conditional truncation). Use parameters from Lemma 8.4. For a symmetric radius-s rule A, s ≥ 1, let PY be its m most probable nonzero labels given Y = Ns−1 (v). Let Akeep retain exactly the original outputs in PY , and let Adel retain exactly the original nonzero outputs outside PY . Other outputs become zero. With τ = p(Adel ) and w = ϵ(Adel ), p(Akeep ) = p(A) − τ,

(15)

keep

(16)

ϵ(A

) + w ≤ ϵ(A), √ 2100 log D τ≤ + 6 w. D

(17)

Both rules preserve symmetry and radius, and the kept rule is conditionally supported on PY ∪ {0}. Proof. Break all ties by coordinate order. The symmetry, support, and occupancy claims follow directly. Couple the rules using the original private draw at each vertex. The conflicts with two kept outputs and those with two deleted outputs are disjoint subsets of the original conflict event. The omitted mixed conflicts are nonnegative, proving (16). Let τY = P[Adel ̸ 0 | Y ]. Every deleted label has conditional probability at most 1/m. Consequently v = tY := tailM (Adel v | Y ) ≥ τY − M/m = τY − η. 22

Put fv = 12 (τYv − 2η)+ and µ = E fv . Then 0 ≤ fv ≤ 1 and τ ≤ 2µ + 2η. At an edge uv with shared view F = Fs−1 (uv) put zuv = tailℓ (Adel u | F ) and Euv = {zuv < fu }, and define the corresponding quantities at v. If fu = 0, failure is impossible. Otherwise tYu > η and fu ≤ tYu /2, so Lemma 8.5 bounds the conditional failure probability, averaged over directions, by δ. Weight by the Yu -measurable fu and then average over Yu . Unconditional branch symmetry gives, for a specified edge, 1 X 1 X E[1Euv fu fv ] ≤ E[1Euv fu ] = E[1Euw fu ] = E[fu Pr[Euw | Yu ]] ≤ δ E[fu ] = δµ. D w∼u D w∼u The same holds at v. When neither Euv nor Evu happens, zuv zvu ≥ fu fv . Proposition 8.2 and Lemma 7.3 imply µ2 2h(µ) − ≤ E[fu fv ] ≤ 4w + q + 2δµ. 2 D If µ < 1/D, then τ < 4/D, which suffices. Otherwise h(µ) ≤ µ log(e/µ) ≤ 2µ log D for large D. Therefore p √ √ 1032 log D 1032 log D µ, µ≤ + 2 2 w + 2q. µ2 ≤ 8w + 2q + D D −2 −1 Using q ≤ D and η = D gives √ √ √ √ 2064 log D 2 2+2 2100 log D τ≤ +4 2 w+ ≤ + 6 w. D D D

In this proof the two endpoint functions fu , fv were never assumed independent. The entropy estimate supplied precisely the lower bound on E[fu fv ] that was needed. Likewise, branch symmetry was used only after averaging over the inner view. There is also an exact version of the conflict bookkeeping. Couple kept and deleted outputs using the same original private draw at each vertex. If x is the probability of a conflict having one kept and one deleted endpoint, counting both orientations, then ϵ(A) = ϵ(Akeep ) + ϵ(Adel ) + x.

(18)

In particular, when ϵ(A) = 0, both restricted rules have zero conflict. Conflicts can first appear when the kept rule is conditionally resampled, not when it is truncated.

9

Warmups to the Final Bound

We now have the two operations needed for iteration: truncation loses little mass unless the deleted part creates conflicts, and conditional resampling removes one round at a controlled information cost. Before using the final accounting, we analyze this iteration in two direct ways.

9.1

Consolidating One-Round Bounds

Start with A0 = A, of radius r, and put Vj (v) = Nr−j (v) for j = 0, . . . , r. At step j < r, let Pj (Vj+1 (v)) be the m most probable nonzero outputs of Aj given the smaller view. Let Cj and Dj be its kept and deleted rules. Obtain Aj+1 by conditionally resampling Cj onto Vj+1 , using new private draws. All these rules retain the required symmetry. Define the numbers pj = p(Aj ),

ϵj = ϵ(Aj ),

τj = p(Dj ) = pj − pj+1 ,

wj = ϵ(Dj ), 2100 log D dj = H((Cj )v | Vj+1 (v)) − H((Cj )v | Vj (v)) ≥ 0, b= . D We suppress v in conditioning notation when no confusion is possible. Propositions 6.1 and 8.6 give q p √ √ τj ≤ b + 6 wj , ϵj+1 ≤ ϵj − wj + 2dj /D. (19) The second inequality uses ϵ(Cj ) ≤ ϵj − wj from (18). Thus ϵj − wj ≥ 0. The final rule Ar has radius zero. 23

Lemma 9.1 (Zero-radius conflict). For a symmetric radius-zero rule, ϵ = p2 /2. Proof. All vertices use the same fixed output distribution. Their private draws are independent of each other and of the central matrix. Both are nonzero with probability p2 , and the selected entry is 1 with probability 1/2. P Lemma 9.2 (Occupancy from a total conflict budget). For the above sequence, put S = ϵr + j<r wj and p = p0 . Then √ √ (20) p ≤ rb + 36r + 2 S. P Proof. The occupancy differences telescope: p = pr + j<r τj . Use (19) and Lemma 9.1 to obtain p ≤ rb + 6

X√

wj +

√

2ϵr .

j<r

Cauchy–Schwarz on these r + 1 terms proves the result. Lemma 9.3 (The cost of accumulating one-step errors). If ϵ0 = 0, then  2 X p 2  2r X S≤ dj  ≤ dj . D j<r D j<r Proof. Put Wj =

(21)

P

i<j wi and Sj = ϵj + Wj . By (19),

r 2dj 2dj + 2 (ϵj − wj ) + Wj + wj Sj+1 ≤ ϵj − wj + D D r  2 q p 2dj 2dj + 2 Sj = ≤ Sj + Sj + 2dj /D . D D Since S0 = 0, induction yields the first inequality. Cauchy–Schwarz yields the second.

9.2

First (Ω̃(D1/3 )) Bound

The kept rule has at most m nonzero coordinates given Vj+1 . Its occupancy is pj+1 ≤ p. Lemma 4.4 and monotonicity give dj ≤ H((Cj )v | Vj+1 ) ≤ p log(em/p). Using this same upper bound at all r steps is legitimate, but it charges a potentially surviving output repeatedly. Proposition 9.4 (A first bound with a cubic term). Under the assumptions of Theorem 1.2, p≤

4200r log D 532r3 log D + . D D

Proof. The preceding estimate and Lemma 9.3 give S ≤ 2r2 p log(em/p)/D. Insert this into Lemma 9.2: s em 76r3 p p ≤ rb + log , D p where 2(36r + 2) ≤ 76r. If r > D or p < 1/D, the m ≤ D4 √claimed bound is immediate. Otherwise 3 and p ≥ 1/D imply log(em/p) ≤ 7 log D. Use Ap ≤ (p + A)/2 with A = 532r log D/D, then rearrange. This is already a growing-round result: it gives p = o(1) for r = o((D/ log D)1/3 ). There are two distinct losses in its accounting. First, we bounded the sum of information costs by r times one worst-case cost. Second, we accumulated square-root errors along the whole chain, producing the factor r in (21). We address the first loss next.

24

9.3

Second (Ω̃(D1/2 )) Bound

Conditional resampling changes uncertainty about unseen inputs into private output randomness. This randomness is still present at the next step; it has not disappeared. Truncation can erase some of it by changing coordinates to 0, but only coordinates actually deleted can cause this loss. The following calculation formalizes this explanation. Lemma 9.5 (Entropy accounting over the entire sequence). For the reduction sequence, X emr emr dj ≤ p1 log ≤ p0 log , p p0 1 j<r

(22)

with zero-mass expressions interpreted as zero. Proof. Write Φj = H((Aj )v | Vj ) for the private output entropy at stage j. For j ≥ 1, the outputs of Aj given Vj lie in Pj−1 (Vj ) ∪ {0}, a set of at most m nonzero coordinates. The same is true for Dj . Set Lj = Φj − H((Cj )v | Vj )

(j ≥ 1).

The kept output is a function of Aj and Vj , while the pair of kept and deleted outputs determines Aj . The chain rule and conditioning therefore give 0 ≤ Lj = H((Aj )v | (Cj )v , Vj ) ≤ H((Dj )v | Vj ) ≤ τj log(em/τj ). By the definition of conditional resampling, Φj+1 = H((Cj )v | Vj+1 ) = H((Cj )v | Vj ) + dj . At j = 0 this reads Φ1 = H((C0 )v | V0 ) + d0 . At j ≥ 1 it reads Φj+1 = Φj − Lj + dj . Telescoping these equalities gives X

dj = Φr − H((C0 )v | V0 ) +

j<r

r−1 X

Lj ≤ pr log(em/pr ) +

j=1

r−1 X

τj log(em/τj ).

j=1

For the last step, Vr is empty and the final output has at most m nonzero coordinates. The r masses pr , τ1 , . . . , τr−1 sum to p1 . If p1 > 0, normalize them to a probability vector α1 , . . . , αr . Then the right side equals p1 log(em/p1 ) + p1

r X

αi log(1/αi ) ≤ p1 log(emr/p1 ).

i=1

The bound on the entropy of an r-valued variable was proved in Section 4. If p1 = 0, all terms vanish. Finally p1 ≤ p0 and x log(emr/x) is increasing on [0, 1]. Proposition 9.6 (A second bound with a quadratic term). Under the assumptions of Theorem 1.2, p≤

4200r log D 532r2 log D + . D D

Proof. Combine Lemmas 9.3 and 9.5 to get S ≤ 2rp log(emr/p)/D. Lemma 9.2 gives s 76r2 p emr p ≤ rb + log . D p If r > D or p < 1/D, the claim is immediate. Otherwise m ≤ D4 , r ≤ D, and p ≥ 1/D imply √ log(emr/p) ≤ 1 + 6 log D ≤ 7 log D. Apply Ap ≤ (p + A)/2 with A = 532r2 log D/D. p This gives p = o(1) for r =Po( D/ log D). The only remaining extra factor in this accounting is the r in the conversion from j dj to S. It comes from following the error of an intermediate rule through every later resampling. We now stop following that chain and instead compare each deleted part directly with a restriction of the original zero-conflict rule. 25

10

Exploiting Multi-Round Entropy Bounds

There are two tasks left. First, show that hiding several layers at once has a cost depending only on the uncertainty remaining in the smaller view. Second, identify an appropriate zero-conflict original rule to which this estimate can be applied for each deletion.

10.1

A Multi-Step Version of Proposition 6.1

The one-step proof in Section 6 used independence of the old endpoint outputs after fixing their shared view. If many layers are hidden, that independence need not hold. The conditional edge-entropy inequality from Section 7 replaces it. Proposition 10.1 (Direct comparison with a smaller-view rule). Let Z be a symmetric radius-R rule, and let 0 ≤ t ≤ R. Define the radius-t rule Q by independent private draws with probabilities P[Qv = a | Nt (v) = y] = P[Zv = a | Nt (v) = y]

(a = 0, . . . , k).

Then p(Q) = p(Z) and r p

ϵ(Q) ≤

p

ϵ(Z) +

2 (H(Zv | Nt (v)) − H(Zv | NR (v))). D

(23)

In particular, if ϵ(Z) = 0, z := p(Z), and at most m nonzero coordinates are possible given each view Nt (v), then 2z em ϵ(Q) ≤ log . (24) D z The last expression is zero at z = 0. Proof. Occupancy is preserved by the law of total probability. Let P be the actual distribution of (Ft , Zu , Zv ), with Ft = {Guv } ∪ Nt (u) ∪ Nt (v). Let Q keep the same Ft distribution and draw the two outputs independently from their smaller-view probabilities. Because both smaller views are determined by Ft , this is precisely the edge distribution of Q. By the first equality of Lemma 4.3, KL(P ∥Q) = 2H(Zv | Nt (v)) − H(Zu , Zv | Ft ). Unlike our other applications of Lemma 4.3, this identity does not require conditional independence of the old outputs. Lemma 7.2 bounds it by
2 H(Zv | Nt (v)) − H(Zv | NR (v)) . D Apply Lemma 4.2 to the conflict event. The central matrix is part of Ft , so the event is identical under the two distributions. This proves (23). When the old conflict is zero, square the inequality, drop the nonnegative full-view entropy, and apply Lemma 4.4. There is no factor R − t in this bound. It is useful when a rule with zero conflict has few possible nonzero coordinates after conditioning on the smaller view. The original rule need not have that property, so we next construct restrictions of it that do.

10.2

Combining Truncation Steps

Return to the sequence from Section 9. Once A0 is fixed, every set-valued function Pj (Vj+1 ) is fixed as well: it is computed from the conditional output probabilities, not from a realized private draw. We can therefore test the same original output against all these lists. At a vertex where A0 outputs a nonzero coordinate a, ask whether a belongs to P0 (V1 ), then to P1 (V2 ), and so on. Record the first rejection, or record that a passes every list. Keep the coordinate unchanged whenever it is recorded.

26

original nonzero coordinate a no

a ∈ P0 (V1 )?

b0 keeps a D

yes no

a ∈ P1 (V2 )?

b1 keeps a D

.. . no

a ∈ Pr−1 (Vr )?

br−1 keeps a D

yes final survivor Abr

Figure 2: Every original nonzero output belongs to exactly one first-failure part or to the final survivor. The coordinate a is unchanged throughout these tests. There are no new output draws in this diagram. Each resulting part is a restriction of the original independent-set selection. Lemma 10.2 (Original survivors have the required conditional probabilities). Use the lists and views of Section 9. On the probability space of the original rule, define ( (A0 )v , (A0 )v ̸= 0 and (A0 )v ∈ Pi (Vi+1 (v)) for every i < j, b (Aj )v = 0, otherwise. bj retain the original nonzero coordinate exactly when it passes every earlier list and fails Pj (Vj+1 ). Let D Then, for every a ∈ {0, . . . , k}, P[(Aj )v = a | Vj ] = P[(Abj )v = a | Vj ], bj )v = a | Vj ]. P[(Dj )v = a | Vj ] = P[(D

(25) (26)

All hatted rules are symmetric radius-r restrictions of A0 . If ϵ(A0 ) = 0, they all have zero conflict. Their first-failure parts and the final survivor partition the original nonzero outputs. For j ≥ 1, the bj , given Vj , belong to a list of at most m coordinates. possible nonzero outputs of Abj and D Proof. Prove (25) for nonzero a by induction. It is immediate at j = 0. The next list depends only on Vj+1 ⊂ Vj . By the definition of the kept rule and of conditional resampling, P[(Aj+1 )v = a | Vj+1 ] = 1{a∈Pj (Vj+1 )} E[P[(Aj )v = a | Vj ] | Vj+1 ] = 1{a∈P (V )} P[(Abj )v = a | Vj+1 ] j

j+1

= P[(Abj+1 )v = a | Vj+1 ]. The middle equality is the induction hypothesis followed by averaging over the larger view. This is the tower property for conditional probabilities. The probability of 0 is the remaining probability. Multiplying the stage-j identity by 1{a∈P / j (Vj+1 )} gives (26) for nonzero a, and hence also for zero. Each hatted output is either the original coordinate or zero, chosen by tests on radius-r matrix data. The tests are symmetric. Conditional on all matrices, the outputs at different vertices still depend on independent original private draws. Thus these are rules in our model. Their conflict events are subsets of the original conflict event. Also, an original nonzero coordinate has a unique first failed test unless it passes them all. Finally, for j ≥ 1, every nonzero output of either hatted rule has passed Pj−1 (Vj ). Once Vj is fixed, this is a fixed list of size at most m. The lemma asserts equality of conditional probabilities, not equality between the realized outputs of a resampled rule and the original rule. That distinction is necessary: the intermediate rules make new private draws. It is enough because a rule in our model is specified by exactly these smaller-view probabilities. 27

10.3

Improved Bound on S

Proposition 10.3 (Joint deleted-conflict budget). Assume ϵ(A0 ) = 0. Recall that pj = p(Aj ), τj = pj − pj+1 , wj = ϵ(Dj ), and ϵr = ϵ(Ar ). Then ϵr +

X

wj ≤

j<r

2p1 log(emr/p1 ) 2p0 log(emr/p0 ) ≤ . D D

(27)

Zero-mass expressions (when p1 = 0 or p0 = 0) are interpreted by continuity. Proof. Use the construction of Lemma 10.2. The first deleted rule is a restriction of the original rule, so w0 = 0. For 1 ≤ j < r, Lemma 10.2 identifies Dj as the radius-(r − j) conditional resampling bj . The latter has zero conflict, occupancy τj , and at most m nonzero labels conditional on Vj . of D Proposition 10.1 gives 2τj log(em/τj ) wj ≤ . D The final survivor Abr has zero conflict and at most m nonzero labels given the empty view Vr . Its radius-zero resampling is Ar , so the same proposition gives ϵr ≤

2pr log(em/pr ) . D

The r masses pr , τ1 , . . . , τr−1 sum to p1 . If p1 > 0, normalize them to a probability vector (α1 , . . . , αr ). The sum of their expressions x log(em/x) equals p1 log(em/p1 ) + p1

r X

αi log(1/αi ) ≤ p1 log(emr/p1 ).

i=1

For p1 = 0 every term is zero. Summing the conflict estimates proves the first inequality. The second follows from p1 ≤ p0 and monotonicity of x log(emr/x) on [0, 1]. The first deleted part is excluded from the entropy sum for a specific reason. Before any resampling has taken place, it already has zero conflict, so w0 = 0. It need not have a short conditional list. Every later first-failure part has passed a previous list, which is what supplies the m-coordinate condition for the direct comparison. Although the hatted parts are all restrictions of one independent-set selection, they are not probabilistically independent of one another. The proof uses their individual zero-conflict property and the fact that their masses form a partition. It makes no independence assumption across parts.

11

Proof of the Final Bound

Proof of Theorem 1.2. Choose an absolute D0 large enough for the parameter bounds, Proposition 8.6, and log D ≥ 1. All thresholds used there are uniform in the finite radius. Start the reduction sequence with A0 = A, and put p = p0 . If p = 0, the claim is immediate. Lemma 9.2 and Proposition 10.3 give s X √ wj p ≤ rb + 36r + 2 ϵr + j<r

r ≤ rb +

76rp emr log , D p

(28) 2100 log D b= , D

using 2(36r + 2) ≤ 76r. The right-hand occurrence of p is the total mass of the original outputs being classified. Thus this is a necessary inequality for the unknown occupancy, not an assumption that it is small. If r > D, then 5000r log D/D ≥ 1, so the probability bound p ≤ 1 suffices. If p < 1/D, the asserted bound also holds. In the remaining case, m ≤ D4 , r ≤ D, and p ≥ 1/D, whence log(emr/p) ≤ 1 + 6 log D ≤ 7 log D. 28

Set A = 532r log D/D. Inequality (28) implies p ≤ rb +

p

Ap ≤ rb +

p A + . 2 2

Subtract p/2 and multiply by 2: p ≤ 2rb + A =

4732r log D 5000r log D ≤ . D D

Combine with p ≤ 1 to finish.

Acknowledgements We thank Shafi Goldwasser, Amir Abboud, Keren Censor-Hillel, Sepehr Assadi, Oded Goldreich, Jason Li, Christoph Grunau, Nikhil Srivastava, Antares Chen, and Peter Davies-Peck for helpful discussions.

12

AI Usage

Many of the key ideas in this work were developed without AI. By December 2024, the authors had identified the hard instance discussed here and shown that no 2-round algorithm for MIS exists on this graph. This 2-round impossibility result used a slightly different strategy from this work. Instead of bounding occupancy and conflict probabilities, it bounded the support size of the algorithm’s output distribution within a given clique. The proof used Proposition 8.2 and Lemma 8.5. The authors wrote up this 2-round impossibility result along with an outline for how to extend the result to Ω(log log n) rounds. All of this was done without AI. Extending the approach seemed doable but tedious, so the authors decided to take a break. The authors decided to try again in September 2026. They assembled one very long prompt containing both (a) the 2-round hardness result and (b) the plan for generalizing to more rounds. After some back and forth, GPT-6 proved the Ω̃(D1/3 )-round hardness result present in this writeup. In particular, GPT-6 came up with the key simplifying idea: tracking occupancy and conflict probabilities instead of support, with round elimination done via truncation and conditional resampling. GPT-6 later produced the Ω̃(D1/2 )-round bound and the final Ω̃(D)-round bound with no additional assistance. GPT-6 then produced a Lean 4 formalization of the proof for Theorem 1.1, which is available at https://github.com/aschild/mis. The authors also used GPT-6 Astra and GPT-6.1 Sol to draft the manuscript, which they subsequently reviewed and revised carefully. The authors take full responsibility for the contents of this paper.

References [1] Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036–1053, 1986. doi: 10.1137/0215074. URL https://doi.org/10.1137/ 0215074. [2] Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. doi: 10.1016/0196-6774(86) 90019-2. URL https://doi.org/10.1016/0196-6774(86)90019-2. [3] Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 350–363. ACM, 2020. doi: 10.1145/3357713.3384298. URL https://doi.org/10.1145/3357713. 3384298.

29

[4] Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2013. ISBN 9781627050180. doi: 10.2200/S00520ED1V01Y201307DCT011. URL https://doi.org/10.2200/S00520ED1V01Y201307DCT011. [5] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. J. ACM, 68(5):39:1–39:30, 2021. doi: 10.1145/3461458. URL https://doi.org/10.1145/3461458. [6] 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. doi: 10.1137/1.9781611974331.CH20. URL https://doi.org/10.1137/1.9781611974331. ch20. [7] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM, 63(3):20:1–20:45, 2016. doi: 10.1145/2903137. URL https: //doi.org/10.1145/2903137. [8] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1–17:44, 2016. doi: 10.1145/2742012. URL https://doi.org/10. 1145/2742012. [9] Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distributed Comput., 22(5-6):363–379, 2010. doi: 10.1007/S00446-009-0088-2. URL https://doi.org/10.1007/s00446-009-0088-2. [10] Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193–201, 1992. doi: 10.1137/0221015. URL https://doi.org/10.1137/0221015. [11] Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discret. Math., 4(3):409–412, 1991. doi: 10.1137/0404036. URL https://doi.org/10.1137/0404036. [12] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhon. Improved distributed network decomposition, hitting sets, and spanners, via derandomization. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2532–2566. SIAM, 2023. doi: 10.1137/1.9781611977554.CH97. URL https://doi.org/10.1137/1.9781611977554. ch97. [13] Mohsen Ghaffari and Christoph Grunau. Faster deterministic distributed MIS and approximate matching. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1777–1790. ACM, 2023. doi: 10.1145/3564246.3585243. URL https://doi.org/10.1145/3564246. 3585243. [14] Mohsen Ghaffari and Julian Portmann. Improved network decompositions using small messages with applications on mis, neighborhood covers, and beyond. In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, volume 146 of LIPIcs, pages 18:1–18:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPICS.DISC.2019.18. URL https://doi.org/10.4230/LIPIcs.DISC.2019.18. [15] 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. URL https://doi.org/10.1109/FOCS61266.2024.00007. [16] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets. SIAM J. Comput., 51(1):70–115, 2022. doi: 10.1137/20M1381770. URL https://doi.org/10. 1137/20m1381770.

30

[17] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed ∆-coloring plays hide-and-seek. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 464–477. ACM, 2022. doi: 10.1145/3519935.3520027. URL https://doi.org/10.1145/3519935.3520027. [18] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 283–293. ACM, 2021. doi: 10.1145/3465084.3467901. URL https://doi.org/10.1145/3465084.3467901. [19] Christoph Lenzen and Roger Wattenhofer. MIS on trees. In Cyril Gavoille and Pierre Fraigniaud, editors, Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 41–48. ACM, 2011. doi: 10.1145/1993806. 1993813. URL https://doi.org/10.1145/1993806.1993813. [20] Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, and Akka Zemmari. An optimal bit complexity randomized distributed MIS algorithm. Distributed Comput., 23(5-6):331–340, 2011. doi: 10.1007/S00446-010-0121-5. URL https://doi.org/10.1007/s00446-010-0121-5. [21] R. Wattenhofer. Mastering Distributed Algorithms. Independently Published, 2020. ISBN 9798628688267. URL https://books.google.bg/books?id=ANJ7zQEACAAJ. [22] Johannes Schneider and Roger Wattenhofer. A log-star distributed maximal independent set algorithm for growth-bounded graphs. In Rida A. Bazzi and Boaz Patt-Shamir, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008, pages 35–44. ACM, 2008. doi: 10.1145/1400751. 1400758. URL https://doi.org/10.1145/1400751.1400758. [23] Seri Khoury and Aaron Schild. Breaking barriers for distributed MIS by faster degree reduction. In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, pages 1037–1048. ACM, 2026. doi: 10.1145/3798129.3800816. URL https://doi.org/10.1145/3798129.3800816. [24] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally! In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 300–309. ACM, 2004. doi: 10.1145/1011767.1011811. URL https://doi.org/10.1145/1011767.1011811. [25] 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. URL https://doi.org/10.1109/FOCS63196.2025.00120. [26] Alkida Balliu, Filippo Casagrande, Francesco d’Amore, and Dennis Olivetti. New hardness results for the local model via a simple self-reduction. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’26, page 301–310, New York, NY, USA, 2026. Association for Computing Machinery. ISBN 9798400725128. doi: 10.1145/3796701.3815938. URL https://doi.org/10.1145/3796701.3815938. [27] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 321–330. IEEE Computer Society, 2012. doi: 10.1109/FOCS.2012.60. URL https://doi.org/10.1109/FOCS.2012.60. [28] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lovász local lemma. In STOC, pages 479–488. ACM, 2016. doi: 10.1145/2897518.2897570. URL https://doi.org/10.1145/ 2897518.2897570.

31

[29] Sebastian Brandt. An automatic speedup theorem for distributed problems. In PODC, pages 379–388. ACM, 2019. doi: 10.1145/3293611.3331611. URL https://doi.org/10.1145/3293611. 3331611. [30] Sebastian Brandt and Dennis Olivetti. Truly tight-in-∆ bounds for bipartite maximal matching and variants. In Yuval Emek and Christian Cachin, editors, PODC, pages 69–78. ACM, 2020. doi: 10.1145/3382734.3405745. URL https://doi.org/10.1145/3382734.3405745. [31] Alkida Balliu, Francesco d’Amore, and Dennis Olivetti. Distributed lower bounds via automatic self-reduction, 2026. URL https://arxiv.org/abs/2609.34753. [32] Ágnes Backhausz, Balázs Gerencsér, and Viktor Harangi. Entropy inequalities for factors of IID. Groups, Geometry, and Dynamics, 13(2):389–414, 2019. doi: 10.4171/GGD/492.

A

Details of the LOCAL Reduction

A.1

Extracting IDs

Lemma A.1 (Independent tentative identifiers). Under the hypotheses of Proposition 3.1, there is a symmetric radius-one function of the edge matrices that assigns tentative identifiers Jv,a ∈ [n] to all vertices of the clique blow-up. These identifiers are mutually independent, and every point has probability at most 2/n. For any fixed clique Cv , the probability of a collision among identifiers in BTH+2 (v) is at most δID . Proof. Partition [k] = P ⊔ Q with |P | = ⌊k/2⌋. For every oriented skeleton edge v → u, flatten Gvu [P, Q] in coordinate order into a string Uv→u of length q = ⌊k 2 /4⌋. On the same undirected edge, Uu→v is obtained from Gvu [Q, P ], transposed. The two blocks are disjoint. All Uv→u are therefore independent uniform strings. L U Let Sv = u∼v v→u . Every Sv is uniform, and different Sv use disjoint strings. Hence the Sv are independent. XOR requires no ordering of the branches and is invariant under coordinatepreserving skeleton isomorphisms. The capacity inequality kbID ≤ q permits splitting the first kbID bits into k independent uniform strings. Interpret string a as Xv,a ∈ {0, . . . , 2bID − 1} and put Jv,a = 1 + (Xv,a mod n). Because n ≤ 2bID < 2n, every identifier has at most two preimages and probability at most 2/2bID ≤ 2/n. Applying separate functions to the independent strings preserves their mutual independence. PT +1 The radius-(T + 2) ball has 1 + D i=0 (D − 1)i skeleton vertices, by the girth assumption, and thus L blow-up vertices. For two distinct vertices x, y, P[Jx = Jy ] ≤ 2/n by independence and the
point-probability bound. Union bound over L2 pairs gives δID . No independence between identifiers and graph edges is claimed.

A.2

Producing Rules

Lemma A.2 (The repaired simulation). For every fixed identifier-indexed tape table W, the candidate and repair construction in Proposition 3.1 defines a symmetric radius-(T + 3) edge-input rule on the infinite D-regular tree. The rule is independent on every matrix realization. Its occupancy at every fixed clique of the finite skeleton H is at most min{1, 5000(T + 3) log D/D}. Proof. At clique Cw , first inspect the tentative identifiers in BTH+1 (w). If any collide, output no candidates. Otherwise simulate the T rounds of A at every vertex of Cw , using the tape indexed by its identifier and port numbers given by the increasing order of neighbor identifiers. All candidate bits are defined before repair. A graph path of length T traverses at most T skeleton edges. Matrices internal to BTH+1 (w) give complete adjacency lists and degrees for vertices over BTH (w). Together with the identifiers there, they also determine all incident port numbers needed by the simulation, including boundary vertices’ ports toward their predecessors. This supplies the full initial data at graph distance at most T , even when neighbor identifiers are given initially. Each tentative identifier requires one additional skeleton layer, so candidates depend only on a radius-(T + 2) matrix view. Retaining a candidate only if it has no candidate neighbor costs one more layer. 32

Adjacent candidates cannot both survive, and a clique contains at most one survivor. Thus return its coordinate, or 0 when there is no survivor. This argument does not use correctness of A on the tentative input. All operations are invariant under permutations of skeleton branches. The tape table is a fixed part of the rule, with no skeleton vertex distinguished by it. The algorithm’s local transition functions may be extended arbitrarily to malformed inputs if necessary. Whenever a candidate gate passes, the local data relevant to its output can instead be completed to a legal n-vertex input: this tree-shaped neighborhood appears in H, and kN ≤ n. Locality makes the simulated output independent of that completion. In particular, the proof assumes no correctness on duplicate identifiers or infinite graphs. Apply Theorem 1.2 on the infinite tree. Since the girth of H is at least 2(T + 3) + 2, every radius-(T + 3) skeleton ball is an induced tree, with the same matrix distribution as its infinite-tree counterpart. The same occupancy bound follows at every fixed clique of H.

A.3

Extracting a Contradictory ID Assignment

Lemma A.3 (Local completion and the tape table). Fix Cv . For every matrix realization, one can choose a legal identifier assignment I v on the padded n-vertex graph, independently of the tape table, such that on the event of distinct tentative identifiers in BTH+2 (v), the repaired edge-input output at Cv agrees with the repaired output of A on this legal input. Conditional on each matrix realization, the assigned private tapes have the distribution of the original randomized algorithm. Proof. On the stated event, preserve all identifiers in BTH+2 (v) and assign the unused identifiers bijectively to the remaining vertices. Outside the event, use any fixed bijection. Both choices may use a fixed external enumeration of vertices; this enumeration is never supplied to the edge-input rule. Order all ports by the completed identifiers. The assignment depends only on the matrices. For w = v or w ∼ v, BTH+1 (w) ⊆ BTH+2 (v). Consequently all candidate gates relevant to repair at Cv pass, and the necessary initial data and tapes agree with those on the completed input. Locality gives the asserted agreement of outputs. The table entries Wi , i ∈ [n], are independent with the original tape distribution and independent of the matrices. The completed identifier assignment is bijective, so, conditional on every matrix realization, (WI v (x) )x is a permutation of this independent table. It therefore has exactly the privatetape distribution of A. No bound on tape length is needed.

A.4

Maximality and Finite Skeletons

Lemma A.4 (External domination). For a fixed clique Cv , the probability that some choice of at most one vertex from each neighboring clique dominates all of Cv is at most γEXT . Outside this graph event, every MIS occupies Cv . Proof. There are (k + 1)D choices, including the empty choice in each neighboring clique. For a fixed choice of j ≤ D vertices, every vertex of Cv is undominated with probability 2−j , independently across the k rows. Thus the chance that this choice dominates every row is at most (1 − 2−j )k ≤ exp(−k2−D ). Union bound gives γEXT . An independent set takes at most one vertex from each neighboring clique. If it leaves Cv empty outside this event, a vertex of Cv has no selected neighbor, contradicting maximality. The graph event quantifies over every external choice, so the selected vertices may depend on the matrices. Lemma A.5 (Regular skeletons of prescribed size; folklore). For integers D, g ≥ 3, put B = 1 + Pg−3 D i=0 (D − 1)i . Every even integer N > 4B admits a simple D-regular graph with girth at least g. Moreover, B ≤ 2Dg−2 . Proof. Among simple graphs on N fixed vertices with maximum degree at most D and girthP at least g, choose one with the largest number of edges. Suppose it is not regular. Total deficiency DN − x deg(x) is a positive even integer. Choose deficient vertices u, v; if there is only one, take u = v, whose deficiency is then at least two. Every deficient vertex other than u is at distance at most g − 2 from u, since otherwise its edge to u could be added. Let U = Bg−2 (u) ∪ Bg−2 (v), so |U | ≤ 2B. Every vertex outside U has degree D. If there were no edge xy with both endpoints outside U , then all D|V \ U | incidences outside would lead into U , giving

33

N ≤ 2|U | ≤ 4B, a contradiction. Delete such an edge xy and add ux, vy; when u = v, add ux, uy. This preserves the degree bound and adds one edge. These new edges are not loops or parallel edges. A cycle containing only one new edge would give an old path from u or v to x or y of length below g − 1, contrary to their distances. A cycle using both new edges either contains an old x–y path in the graph with xy deleted, or contains two old paths from {u, v} to {x, y}. In the first case that path has length at least g − 1 by the old girth; in the second case both paths do by distance. The same first case covers u = v. Hence no cycle of length below g is introduced, P contradicting maximality. The graph was g−2 regular. Finally, the maximum-degree ball bound gives B ≤ i=0 Di ≤ 2Dg−2 .

A.5

Reduction Parameters

Lemma A.6 (Parameter checks for the LOCAL lower bound). Fix 0 < σ ≤ 1. Let n tend to infinity, and let T be any nonnegative integer satisfying T < σ log n/(100000 log log n). For the parameters D, k, N, g in the proof of Theorem 1.1, all the graph and parameter hypotheses of Proposition 3.1 hold, for a suitable skeleton H, for sufficiently large n. Its error terms satisfy δID = o(1) and nγEXT = o(1), uniformly over these choices of T . Proof. We have D = (log n)/4 + O(1) and k = n1/4+o(1) . In particular D ≥ D0 , D ≤ log k ≤ D2 , and kN ≤ n for large n. Since bID = O(log n) while k is a positive power of n, also kbID ≤ ⌊k 2 /4⌋. The integer N is even and N = n3/4+o(1) . For the ball bound B in Lemma A.5, log(4B) ≤ log 8 + (2T + 6) log D ≤ (2σ/100000 + o(1)) log n. Thus N > 4B, and that lemma supplies the required D-regular skeleton of girth at least g = 2T + 8. The local ball contains at most 2DT +2 skeleton vertices, so L ≤ 2kDT +2 and δID ≤ L2 /n ≤ n−1/2+2σ/100000+o(1) = o(1). Finally, k + 1 ≤ eD+1 and k ≥ eD for large D. Hence log(nγEXT ) ≤ log n + D(D + 1) − e(1−log 2)D −→ −∞. All remainders and thresholds above depend only on σ and the absolute constants. The stronger estimate nγEXT = o(1) also justifies the introductory claim that, with high probability, every MIS intersects every clique simultaneously: union bound over N ≤ n cliques.

34

Related documents

• No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model#1343731
• Stochastic Caching via Subset Entropy / Ravi Kumar, Roie Levin, Joseph (Seffi) Naor, Debmalya Panigrahi#1188640
• Breaking the Infinite Barrier in the $\frac{1}{3}$--$\frac{2}{3}$ Conjecture#1105447
• A Simpler Proof of Kakutani's Conjecture on Random Subdivision and Its Generalizations#986790
• Randomized Algorithms#3284