arXiv CSopen access

Distributed Lower Bounds via Automatic Self-Reduction

Alkida Balliu et al. · arxiv_cs

arXiv CS · Papers · License: Open Access

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Distributed Lower Bounds via Automatic Self-Reduction Alkida Balliu · Gran Sasso Science Institute Francesco d’Amore · Gran Sasso Science Institute

arXiv:2609.34753v1 [cs.DC] 28 Sep 2026

Dennis Olivetti · Gran Sasso Science Institute

Abstract. The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds of ω(log log n) rounds as a function of the number n of nodes. Very recently, Khoury and Schild [FOCS 2025] introduced a new technique called round elimination via self-reduction, which bypasses the limitations of classical round elimination. Using this √ approach, the authors show that any randomized algorithm for maximal matching requires Ω( log n) rounds in the LOCAL model. Their elegant technique is, in some respects, similar to classical round elimination while being fundamentally different in others. However, it is tailored specifically to maximal matching rather than being applicable to a broad class of problems. In this paper, we show that self-reduction is, in fact, a special case of classical round elimination, thereby turning it into a general-purpose approach. In particular, we introduce a new way to measure the error of an algorithm and show that, under this new measure, classical round elimination can indeed yield ω(log log n) randomized lower bounds. More specifically, we identify a large class of problems for which this improvement is entirely black-box: once a problem is shown to belong to the class, stronger randomized lower bounds follow √ automatically from the classical round-elimination framework. As an application, we prove Ω( log n) randomized lower bounds for a range of graph problems, namely, maximal matching on regular 2-colored graphs, k1 -integral matching, and maximal H-packing.

Introduction

In the distributed setting, the network is represented by a graph in which nodes model computing entities and edges represent communication links. One of the most studied models of distributed computation is the LOCAL model. This is a synchronous message-passing model; computation proceeds in synchronous rounds, where in each round nodes exchange messages with their neighbors and then perform local computation. Neither the message size nor the computational power of individual nodes is restricted. Each node has a unique identifier and, when randomness is allowed, each node has access to an unbounded string of random bits. When studying problems in this model, the focus is on communication, and the goal is to understand how many rounds of communication are sufficient, or necessary, in order to solve a graph problem. The LOCAL model captures the locality of distributed graph problems: how far must information travel through a network in order to solve a given problem? Understanding the locality of fundamental graph problems in the distributed setting has been at the center of attention since the field’s beginnings. Over the years, researchers have studied the locality of graph problems as a function of both the number n of nodes and the maximum degree ∆ of the graph. Collective efforts have focused both on developing algorithms with tighter upper bounds and on proving stronger lower bounds. For example, the best upper bound for maximal matching,1 expressed as a function of n and ∆, has been known since 2001 [PR01]. However, the optimality of this algorithm was established only 18 years later [BBH+21]. Part of the reason why this result took so long to establish is the fact that the LOCAL model is very powerful, making it quite challenging to prove lower bounds. Yet, it is also highly rewarding, as lower bounds for the LOCAL model directly carry over to weaker models of distributed computing. Another key reason was the lack of general-purpose lower bound techniques: developing broadly applicable techniques can indeed be difficult, but it is sometimes the best way to gain a more comprehensive and deeper understanding of problems of interest. For several natural graph problems, the first polylogarithmic randomized LOCAL lower bounds were established back in 2004 using the celebrated KMW construction [KMW16]. At the core of this technique are arguments based on the notion of indistinguishability. At a very high level, the KMW lower bounds are obtained by showing that, if the running time of the nodes is too small, then there are many nodes in the construction that have identical information about the graph and hence have the same output distribution. Such behavior is problematic for problems that require breaking symmetry between nodes or edges, such as maximal matching or maximal independent set, and thus leads to lower bounds for such problems. As time has shown, obtaining lower bounds via indistinguishability arguments appears to be quite challenging for certain symmetry-breaking problems of interest. In fact, apart from the KMW construction and its closely related variants [CL21, BGK+22], there are no genuinely new constructions yielding lower bounds via indistinguishability. An important turning point in the development of lower bounds for symmetry-breaking problems in the LOCAL model (and, consequently, in our understanding of the distributed complexity of such problems) came when an old technique called round elimination [Lin92] was extended into a general-purpose technique. Round elimination. The successful development of round elimination into a general-purpose technique dates back to 2019 [Bra19]. Broadly speaking, this technique is based on the following idea. Assume that a problem Π0 of interest can be solved in T rounds. The goal is to construct a 1

The maximal matching problem asks for a subset of edges that share no endpoints (that is, an independent set of edges) such that adding any other edge to the set would violate this requirement. By best here we mean the upper bound that minimizes the dependence on n, at the cost of a larger dependence on ∆.

lower bound sequence of problems Π1 , Π2 , . . . , ΠT such that each problem Πi can be solved in T − i rounds. In particular, ΠT can be solved in 0 rounds. If we then show that ΠT cannot be solved in 0 rounds, we obtain a chain of contradictions and conclude that Π0 cannot be solved in T rounds. Given a problem Π0 , the sequence of problems used to prove the lower bound can be constructed in a mechanical way. That is, there exists a function R that takes as input a problem Π and outputs a problem Π′ that, under some conditions, is exactly one round easier than Π. Unfortunately, often the description of Π′ is exponentially larger than that of Π, making it practically impossible to obtain a useful lower bound. In some cases, however, the problems remain the same, i.e., R(Π) = Π. Clearly, Π cannot be exactly one round easier than itself, so this implies some kind of contradiction. The contradiction is on the conditions required to conclude that R(Π) is one round easier than Π, and we know that, if such conditions do not apply, then Π is in some sense hard. If R(Π) = Π, we say that Π is a fixed point under the round elimination framework. For example, the perfect matching problem (i.e., finding a matching in which every node is matched) is a fixed point, whereas maximal matching is not a fixed point. The general-purpose aspect of the round elimination technique has been key for obtaining many breakthrough lower bound results and has substantially advanced our understanding of the complexity of several important graph problems [BBB+24, BBE+20, BBK+21, BBH+21, BBK+23, BBC+25, BBK+25, BBG+26, BBO22, BHO+19, BO20, BFH+16, BBK+26]. The lower bounds in the LOCAL model obtained using the broadly applicable round elimination technique are tight for some problems. For other problems, however, these bounds are not tight. In fact, if we consider randomized algorithms and focus on expressing the complexity of graph problems solely as a function of n, the KMW construction establishes, for many problems of interest, a stronger lower bound than the one obtainable via the current round elimination technique. For example, if we focus on randomized algorithms that solve the maximal matching problem in the LOCAL model, the two techniques give the following bounds. q log n • KMW proves a lower bound of Ω log log n rounds; • The current round elimination technique gives a lower bound of Ω

log log n log log log n

rounds.

A new lower bound technique: self-reduction. In 2025, Khoury and Schild introduced a new technique that they called round elimination via self-reduction [KS25]. Using this technique, they improved the KMW lower bound for maximal matching, showing that any randomized algorithm √ that solves the problem in the LOCAL model requires Ω log n rounds. It took 21 years to improve the lower bound for such a fundamental problem. At a high level, the lower bound is proved as follows. Assume that we can produce a sufficiently large matching, which may not be maximal, in T rounds in the LOCAL model. It is possible to show that, in T − 1 rounds, we can produce a matching that still matches many nodes (in other words, the matching produced in one round less is not much smaller). Iterating this argument, starting from a sufficiently small value of T , would yield a 0-round algorithm that produces a matching larger than is possible without communication. This gives a contradiction, establishing a lower bound of T + 1 rounds. Like the round elimination technique, self-reduction examines what happens when we eliminate one round. However, while maximal matching is not a fixed point under the round elimination framework, self-reduction does not change the problem studied when moving to one round less: it remains a matching problem. Thus, unlike classical round elimination, self-reduction keeps the problem itself unchanged, hence the name “self-reduction”. The self-reduction technique immediately attracted lots of attention because new techniques for proving lower bounds in the LOCAL model can pave the way for understanding the locality of 2

many graph problems, especially if they can be developed into general-purpose techniques. Round elimination is a striking example of this phenomenon. The original formulation and analysis of the self-reduction technique were quite complex. Shortly after its publication, was p the technique significantly simplified and then extended to establish a lower bound of Ω log1+b n rounds for the more general maximal b-matching problem [BCd+26]. While this was a valuable step towards better understanding self-reduction, the goal of obtaining a general-purpose technique remained far from being achieved. Since then, several researchers (including the authors of this paper) have put considerable effort into understanding the power of this technique and tried to apply it to other symmetry-breaking problems, but these attempts have consistently encountered technical obstacles. Limitations of current round elimination. Being able to obtain randomized lower bounds of ω(log log n) rounds directly via classical round elimination would represent a major advance. Indeed, since round elimination is a general-purpose technique, such a result could pave the way for proving randomized lower bounds of ω(log log n) rounds for many different problems. However, efforts to achieve this goal have been unsuccessful so far, suggesting that this may be a limitation of the technique itself. In fact, Khoury and Schild explicitly express this intuition in their paper [KS25]. “While this approach [round elimination] has been very successful for several problems, including leading to the state-of-the-art lower bounds for deterministic algorithms, its performance is limited as a function of n for randomized ones.” The fundamental question of whether it is possible at all to prove randomized lower bounds of ω(log log n) rounds via classical round elimination has remained open since 2019 and was explicitly posed in 2022 as Open Problem 6 in [BBK+22, BBK+26].

1.1

Our Contribution in a Nutshell

In this paper, we provide a deep understanding of self-reduction and we turn it into a general-purpose technique. More precisely, we show that the self-reduction technique is a special case of the classical round elimination technique. To achieve this result, we first characterize a vast class of problems for which the self-reduction technique works. We then improve the round elimination technique to prove, for this entire class of problems, a stronger lower bound than what was previously obtainable via round elimination. To establish our results, we advance our understanding of round elimination in two directions. First, we introduce a new way to measure an algorithm’s error (that is, a new way to count the incorrect outputs produced by the algorithm), enabling a more fine-grained analysis of its failure probability. This alone, however, is not sufficient. We also introduce a new way to construct a (T − 1)-round algorithm from a T -round one, significantly different from the usual way. However, the class of problems for which we obtain the above-mentioned results includes only rigid “global” problems, such as perfect matching and 2-vertex coloring. It is already known that these problems, if solvable at all, require Ω(D) rounds in the LOCAL model, where D is the diameter of the graph. We also know that any solvable problem in the LOCAL model can be solved in O(D) rounds. Hence, it is natural to ask: What is the value of obtaining a stronger lower bound via round elimination for these problems when we already know an asymptotically tight lower bound? What is the relationship between rigid global problems and local problems? More specifically, how can a stronger lower bound obtained via round elimination for perfect matching imply a stronger lower bound for the much easier problem of maximal matching? The answers to the above questions lie in a fundamental difference: an Ω(D) lower bound applies only when the algorithm is required to fail with very small probability; in contrast, our technique 3

yields lower bounds as a function of the target error of the algorithm, with a dependence that scales well with the error parameter. Note that standard round elimination also gives lower bounds that depend on the target failure probability, but this dependence is substantially weaker than the one we obtain in this paper. Let us compare the lower bounds that we get using our technique with those obtained via standard round elimination. Let p be the target local failure probability. With standard round elimination, we obtain lower bounds of 1 Ω min log∆ log , log∆ n rounds, p whereas our new error measure and algorithm definitions yield a lower bound of 1 rounds. Ω min log , log∆ n p For the moment, let us ignore the log∆ n term, which becomes relevant only when p is very small. Our lower bounds represent more than an exponential improvement over the standard ones. Indeed, an exponential improvement alone would improve the first term only to log∆ p1 , whereas our lower bound additionally removes the dependence on ∆ from the base of the logarithm. It is precisely the absence of this dependence on ∆, together with the exponential improvement, that enables us to prove lower bounds for problems outside the class of rigid problems mentioned above. As an example, let us focus on maximal matching (a problem outside the class) and perfect matching (a problem in the class). First, we observe that there exist families of graphs in which any maximal matching leaves at most an O(log ∆/∆) fraction of the nodes unmatched. On these graphs, we can transform any algorithm that solves maximal matching into an algorithm that solves perfect matching with sufficiently small error (i.e., an O(log ∆/∆) fraction of nodes produce an incorrect output), without increasing the running time. Our refined analysis, together with our new definitions, immediately implies that√any randomized algorithm that solves perfect matching with sufficiently small error requires Ω log n rounds in the LOCAL model. This implies the same lower bound for maximal matching. As a consequence of our results, all previously known lower bounds obtained via self-reduction follow as simple corollaries. Moreover, we prove new lower bounds for a range of graph problems, namely maximal matching on bipartite regular 2-colored graphs, 1/k-integral matching, and maximal H-packing. In the latter problem, given a constant-size graph H, the goal is to find a maximal collection of vertex-disjoint copies of H in the input graph. As with randomized lower bounds obtained via round elimination in general, our lower bounds hold even when nodes have access to shared randomness. √ In summary, we establish the first Ω log n lower bounds directly via standard round elimination, showing that classical round elimination can yield stronger lower bounds than those obtained via KMW, even when the complexity is expressed solely as a function of n. This demonstrates that previous attempts to prove stronger lower bounds via round elimination failed because of insufficiently precise analyses and definitions, rather than because of an inherent limitation of the technique itself. This also resolves Open Problem 6 in [BBK+26] in the affirmative. To fully describe our results and the new technical insights behind them, we must first explain round elimination (and fixed points) in more detail, define the class of problems for which we obtain stronger lower bounds via round elimination, and give some useful definitions. We would like to point out that the results obtained in this paper would not have been possible without the beautiful ideas and techniques of Khoury and Schild [KS25]. 4

High-Level Ideas, Results, and Technical Insights

In this paper, we show that the result of Khoury and Schild [KS25] can be obtained via standard round elimination, and we use the resulting insights to characterize the class of problems to which this approach applies. We start by explaining the round elimination technique in more detail.

2.1

A Summary of Round Elimination

The round elimination technique does not work directly in the LOCAL model, but rather in the deterministic version of a weaker model called the port-numbering model. In this setting, the computational power of each node and the message size remain unrestricted. However, nodes have neither unique identifiers nor access to randomness. At each node v, the incident edges are assigned distinct port numbers from 1 to deg(v), in some arbitrary order, where deg(v) is the degree that v has in the graph. Round elimination works in this setting as follows. There exists a function R that takes as input a problem Π defined in the so-called black-white formalism, and outputs a problem R(Π) that is still defined in the black-white formalism (the details of this formalism are not important at this point; we will however define it shortly in Definition 2.4). This function guarantees that, if Π has complexity T in the deterministic port-numbering model, and T is sufficiently small compared to the girth of the graph, then R(Π) has complexity max{T − 1, 0}. Some problems satisfy an interesting property: R(Π) = Π. These problems are called fixed points. Note that, if Π cannot be solved in 0 rounds, this is a clear contradiction, and we can conclude that T cannot be sufficiently small compared to the girth of the graph. By picking suitable graph families, we obtain a lower bound of Ω(log∆ n) rounds (recall that n denotes the number of nodes and ∆ the maximum degree of the graph). In summary, if a nontrivial problem Π satisfies R(Π) = Π, we immediately obtain a lower bound of Ω(log∆ n) rounds in the deterministic port-numbering model. However, what we really want are lower bounds in the much stronger randomized LOCAL model. For this purpose, we can use existing black-box lifting theorems that lift such lower bounds to the randomized LOCAL model. In fact, the following is known. Theorem 2.1 ([BBK+26, BBG+26]). Let Π be a problem described in the black-white formalism using L labels. Assume that R(Π) = Π and that Π cannot be solved in 0 rounds in the deterministic port-numbering model. Then, Π requires Ω(log∆ n − log∆ log L) rounds in the deterministic LOCAL model, and Ω(log∆ log n − log∆ log L) rounds in the randomized LOCAL model, for algorithms with failure probability at most 1/n. For problems where L is at most 2O(∆) , we directly get a randomized LOCAL lower bound of Ω(log∆ log n) rounds. As a side note, one can make such black-box lifting theorems parametric in the desired local failure probability. Indeed, the following is also known. Theorem 2.2 ([MRS+26]). Let Π be a problem that satisfies R(Π) = Π and that cannot be solved in 0 rounds in the deterministic port-numbering model. Also, n oassume that the number of labels of 1 O(∆) Π is in 2 . Then, Π requires Ω min log∆ n, log∆ log p − O(1) rounds in the randomized LOCAL model, for algorithms with local failure probability at most p. The above black-box lifting theorems are proved by showing the following statement, and applying it recursively. Lemma 2.3 ([BBE+20, GRB22], informal). Suppose Π can be solved in T rounds with local failure probability 1 p. Then, R(Π) can be solved in T − 1 rounds with local failure probability at most O p ∆+1 . 5

In other words, the lemma shows that, for randomized algorithms, we can save one round at the cost of increasing the local failure probability polynomially. An important observation is that applying these black-box lifting theorems within the round elimination framework cannot yield lower bounds stronger than Ω(log∆ log n) rounds. More generally, for algorithms with local n failure probability o at most p, these theorems cannot establish lower bounds 1 stronger than Ω min log∆ n, log∆ log p rounds. For some problems, such as sinkless orientation, this lower bound is tight. As a consequence, these black-box lifting theorems cannot be improved without restricting the class of problems: there cannot be a lifting theorem that applies to all problems satisfying R(Π) = Π and that gives an ω(log∆ log n) lower bound. Hence, a stronger lifting theorem requires additional restrictions on the class of problems.

2.2

Problem Family

To describe the family of problems we consider, we first need to provide the definition of the black-white formalism used in the round elimination framework. Definition 2.4 (Problems in the black-white formalism). A problem Π in the black-white formalism is a tuple (Σ, ∆, δ, CW , CB ) where: • Σ is a finite set of labels. • CW is a set of multisets, each of size ∆, of labels from Σ. • CB is a set of multisets, each of size δ, of labels from Σ. Elements of CW and CB are called configurations. Solving a problem Π = (Σ, ∆, δ, CW , CB ) in a (∆, δ)-biregular 2-colored graph means assigning a label from Σ to each edge such that: • For each white node v, the multiset of labels assigned to the edges incident to v forms a configuration present in CW . • For each black node v, the multiset of labels assigned to the edges incident to v forms a configuration present in CB . Throughout the paper, we assume that the set of labels appearing in CW and the set of labels appearing in CB are the same (otherwise there would be configurations that cannot be used at all, and we normalize the problem by removing them), and are exactly Σ. Moreover, we assume that CW and CB are non-empty. Note that, with this formalism, it is possible to define problems on standard non-2-colored graphs: nodes become white nodes, then we put a black node in the middle of each edge, and we require to output a label for each node-edge pair. This variant, which is essentially the restriction to the case δ = 2, is called node-edge formalism. Figure 1 illustrates the perfect matching problem in both formalisms. Family of problems. Our improved black-box lifting theorem applies to all problems in the black-white formalism in which any two distinct configurations have edit distance at least 2. If, in addition, each configuration has a so-called dominant label, we obtain stronger lower bounds. We now define these concepts formally.

U M

U U

U M

M M

U U

CW = {M, U, U} , CB = {M, U, U} .

CW = {M, U, U} , CB = {M, M}, {U, U} .

(a) Black-white formalism.

(b) Node-edge formalism.

Figure 1: Perfect matching in the two formalisms, illustrated on the same 3-regular graph. Thick blue edges are matched; all other edges are unmatched. In (a), each edge has one label, and every white and black node sees exactly one M. In (b), each node-edge pair has a label; every node sees exactly one M, and the two labels on each edge agree. Subdividing each edge in (b) by a black node gives its black-white representation, with white degree 3 and black degree 2. Definition 2.5 (Distance between configurations). Let C be a configuration, and let mC (ℓ) denote the multiplicity of ℓ in C. For two configurations C1 and C2 of the same size, we define their distance as 1X d(C1 , C2 ) = |mC1 (ℓ) − mC2 (ℓ)|, 2 ℓ

that is, the minimum number of label substitutions needed to transform one configuration into the other, or, equivalently, the edit distance between C1 and C2 . We extend this notion to define the distance between a configuration and a set of configurations in the standard way. Definition 2.6 (Distance from a set). Let C be a nonempty set of configurations, and let C1 be a configuration. Then, the distance from C1 to C is defined as d(C1 , C) = min d(C1 , C2 ). C2 ∈C

Definition 2.7 (2-separated problems). Let Π = (Σ, ∆, δ, CW , CB ) be a problem in the black-white formalism. We say that Π is 2-separated if the following holds. • Let C1 , C2 ∈ CW . If C1 ̸= C2 , then d(C1 , C2 ) ≥ 2. • Let C1 , C2 ∈ CB . If C1 ̸= C2 , then d(C1 , C2 ) ≥ 2. Perfect matching, 2-vertex coloring, even orientations are examples of 2-separated problems. Instead, maximal matching, maximal independent set, sinkless orientation are examples of problems that are not 2-separated. Definition 2.8 (b-dominant problems). Let b ≥ 0 be an integer. Let Π = (Σ, ∆, δ, CW , CB ) be a problem in the black-white formalism. We say that Π is b-dominant if the following holds: 7

• Let C ∈ CW . There exists a label ℓ such that mC (ℓ) ≥ ∆ − b. • Let C ∈ CB . There exists a label ℓ such that mC (ℓ) ≥ δ − b. Observe that any problem in the black-white formalism is max{∆, δ}-dominant.

2.3

A New Measure of Error

Typically, the local failure probability of a node is defined as the probability that the node produces an invalid configuration, and the global failure probability is defined as the probability that at least one node fails. Using this standard notion of failure (which is the one used in the existing lifting theorems) we cannot achieve our results. In fact, one of our main contributions is proposing a novel and more fine-grained notion of error. In order to distinguish the two notions, we use the term failure for the standard one, and error for the one we introduce. Definition 2.9 (Error of an algorithm). Let Π = (Σ, ∆, δ, CW , CB ) be a problem in the black-white formalism. Let G = (W, B, E) be a (∆, δ)-biregular 2-colored graph, and let f : E → Σ be a label assignment to the edges of G. For a node v, let c(v) be the configuration induced by the assignment of f to the edges incident to v. The error of f w.r.t. Π is defined as: X X d c(v), CW + d c(v), CB v∈W

v∈B

We call the first term white error and the second term black error. By expected error of an algorithm A on G we denote the expected error taken over all possible assignments of random bits to the nodes of G. In other words, if a node fails, we do not simply count it as a failed node; instead, we measure its error by the minimum number of labels around it that must be changed to correct its output. Note that, however, this measure does not take into account any new errors that these changes around a node might introduce elsewhere.

2.4

A New Lifting Theorem for Round Elimination

We are now ready to state our main result about round elimination. Theorem 2.10 (Informal). Let Π be a b-dominant 2-separated problem. Let ε0 be a lower bound on the expected error for Π. Then, any algorithm for Π with error at most ε of any 0-round algorithm requires Ω min log∆ n, log2+b ε0 /ε rounds in the randomized LOCAL model. We emphasize that Theorem 2.10 is not obtained by merely refining the analysis of the existing black-box lifting theorems in the case of 2-separated problems and under the new notion of failure probability. To achieve it, we introduce a different way to define the (T − 1)-round algorithm. In the following, we observe some consequences of our result. For ease of presentation, let us first simplify a bit the setting. Let us temporarily set aside the distinction between error and failure and assume that Theorem 2.10 talks only about failure probability (even though this is not quite precise). Assume also that ∆ ≥ δ. Notice that, under this assumption, any problem in the black-white formalism is ∆-dominant. We observe the following. • Let p be the desired local failure The standard o black-box lifting theorems give probability. n 1 randomized lower bounds of Ω min log∆ n, log∆ log p rounds. As discussed, this bound cannot be improved without restricting the class of problems to which the theorem applies. 8

• We show problems, we can improve this bound exponentially, to n that, for 2-separated o 1 Ω min log∆ n, log∆ p rounds. also O(1)-dominant, we obtain an even stronger result, establishing a lower • If the problem is n o 1 bound of Ω min log∆ n, log p rounds. While generalizing the lower bound to obtain a better dependence on p may seem like a small detail, we note that such an improvement has important consequences: in fact, it enables us to prove lower bounds for problems that are not even 2-separated!

2.5

Applications

Now that we have provided formal definitions, we revisit the maximal matching example in more detail. Maximal matching, when encoded in the black-white formalism, is not 2-separated. However, perfect matching is. It is known that there are families of regular graphs with girth Ω(log∆ n) and independence number O(n log ∆/∆). Since the unmatched nodes in any maximal matching form an independent set, every maximal matching on such graphs leaves at most an O(log ∆/∆) fraction of the nodes unmatched. We transform any algorithm that solves maximal matching on these graphs into an algorithm that, in the same running time, solves perfect matching with sufficiently small errors. The transformation is simple: each unmatched node arbitrarily chooses an incident edge and marks it as matched. Notice that the resulting algorithm never makes errors at nodes; errors occur only on edges, and the total number of errors is O(n log ∆/∆). Hence, the expected error is ε = O(n log ∆/∆). Also, it is easy to see that any 0-round algorithm for perfect matching makes Ω(n) errors in expectation. Since perfect matching is a 1-dominant 2-separated problem, we directly obtain a lower bound of Ω (min {log∆ n, log(∆/ log ∆)}) = Ω (min {log∆ n, log ∆}) rounds for maximal matching. In other words, we can use a simple graph theoretic argument, combined with our black-box lifting theorem, and obtain lower bounds for local problems. While the example was for algorithms that never fail, even if we consider Monte Carlo algorithms with global failure probability at most 1/n, we can alter the solution (without spending any additional round) so that every node is happy and errors are on edges, while introducing O(1) additional expected errors, and hence the same idea goes through. We apply our technique to two families of problems. The first generalizes standard maximal matching to a fractional setting, where the goal is to assign each edge a weight in [0, 1] such that the sum of the weights of the edges incident to each node is at most 1, and no edge weight can be increased without violating this constraint. A node is considered matched if the sum of its incident edge weights is exactly 1. We restrict our attention to the case where outputs are restricted to integer multiples of 1/k, for some constant k independent of n and ∆, and prove the following theorem. 1 Theorem 2.11. Let k be a positive integer fixed independently of ∆ and n. Maximal k -integral √ matching requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized LOCAL model, for any algorithm with failure probability at most 1/n. These lower bounds hold even on ∆-regular graphs of girth Ω(log∆ n).

The second family of problems generalizes matching in a totally different way. We can see matching as the problem of packing a maximal set of copies of the graph consisting of two nodes that share an edge. A generalization of this view is maximal H-packing, where we use different graph patterns.

Theorem 2.12. Let H be a tree with at least 2 nodes fixed independently of ∆ and n. The maximal √ H-packing problem requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized LOCAL model, for any algorithm with failure probability at most 1/n. These lower bounds hold even on ∆-regular graphs of girth Ω(log∆ n). Maximal matching on 2-colored graphs has been extensively studied. The best randomized lower bound as a function of n is given by the KMW construction [KMW16] (in fact, the lower bound of Khoury and Schild [KS25] does not directly apply in such graphs). We show that a simple graph-theoretic argument, combined with our new lifting theorem, yields an improved lower bound for maximal matching also on bipartite 2-colored graphs. Theorem 2.13. The maximal matching problem, on bipartite ∆-regular 2-colored graphs of girth √ Ω(log∆ n), requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized LOCAL model, for any algorithm with failure probability at most 1/n. Limitations. In some sense, our new black-box lifting theorem cannot be improved. More precisely, we show that requiring problems to be 2-separated is, in a certain sense, necessary. However, we do not claim that b-dominance is necessary. Nevertheless, we show that there are problems that are not o(∆)-dominant and that admit an algorithm with complexity O log∆ εε0 . This implies that there cannotexist a black-box lifting theorem for all 2-separated problems that gives a lower bound of Ω min log∆ n, log εε0 rounds without imposing some additional restriction. We show that O(1)-dominance is sufficient, although other notions may be sufficient as well. We formalize these limitations in the following theorems. Theorem 2.14 (Informal). Without 2-separation, our round-elimination analysis cannot guarantee, in general, that saving one round increases the error by only a multiplicative factor depending on ∆ and δ. Theorem 2.15. There exists a problem Π that is 2-separated, not o(∆)-dominant, and that can be solved in T ∈ O 1 + log∆ εε0 rounds in the randomized LOCAL model in graphs of girth Ω(log∆ n) with target error at most ε, where ε0 ∈ Ω(n) is a lower bound on the expected error of any 0-round algorithm for the problem that has 0 white error, assuming ε is chosen such that T ∈ o(log∆ n).

Road Map

The paper is structured as follows. In Section 4, we provide some basic notions, and we define the function R. In Section 5, we prove Theorem 2.10, our new black-box lifting theorem for round elimination. In Section 6, we provide applications. We first provide a generic helper theorem, that connects local problems to global problems. Then, we apply it to prove Theorem 2.11 (the lower bound for k1 -integral matching), Theorem 2.12 (the lower bound for maximal H-packing), and Theorem 2.13 (the lower bound for bipartite maximal matching). In Section 7, we prove Theorem 2.14 (2-separation is required) and Theorem 2.15 (2-separation is not sufficient to improve log∆ ε0 /ε to log ε0 /ε). We conclude in Section 8 with some open questions.

Preliminaries

LOCAL model. The LOCAL model of distributed computation is a synchronous message-passing model, first introduced by Linial [Lin92]. Typically, it is assumed that each node has an ID that 10

is unique in the entire graph, and that nodes know beforehand their own ID, their degree in the graph, the maximum degree ∆, and the total number n of nodes in the graph.2 The computation proceeds in synchronous rounds. In each round, nodes exchange (possibly different) messages with their neighbors and perform local computation. The size of the messages and the amount of local computation performed by each node are not restricted. The runtime of an algorithm solving a graph problem in the LOCAL model is measured as the number of communication rounds needed for all nodes to produce their output. In the randomized version of the LOCAL model, nodes have access to a string of random bits of unrestricted size. As in the case of the port numbering model, nodes also have access to ports, i.e., an algorithm running on v can e.g. refer to its ith incident edge. However, we assume that these ports are not given adversarially: they are assigned by the nodes using their own random bits (this is w.l.o.g., as any adversarial assignment could be replaced by a random assignment by the algorithm at the beginning of the computation). Our lower bounds apply to Monte Carlo algorithms. Any T -round Monte Carlo algorithm that solves a graph problem in the randomized LOCAL model must produce a solution within T rounds, and the solution must be correct with high probability, i.e., with probability at least 1 − 1/n. For technical reasons, we assume that nodes are not given IDs in the randomized LOCAL model. Note that this does not weaken the model (or our results), as nodes can always generate unique IDs with failure probability at most 1/nc , for any arbitrary c > 0, without communication, and hence this does not change the failure probability by much. Round elimination. Let Π = (Σ, ∆, δ, CW , CB ) be a problem in the black-white formalism. The ′ , C ′ ) defined as follows. function R(Π) gives a new problem Π′ = (Σ′ , δ, ∆, CB W • Let C ′ be the set of multisets {L1 , . . . , Lδ } satisfying that, for all i, Li ⊆ Σ and Li ̸= {}, ′ be the subset of C ′ and that ∀ℓ1 ∈ L1 , . . . , ℓδ ∈ Lδ , it holds that {ℓ1 , . . . , ℓδ } ∈ CB . Let CB containing only maximal configurations, that is, all configurations C = {L1 , . . . , Lδ } ∈ C ′ such that there is no other configuration C ′ = {L′1 , . . . , L′δ } ∈ C ′ such that C ′ ̸= C and there exists a bijection ϕ such that, for all i, Li ⊆ L′ϕ(i) . ′ . • Σ′ is the set of sets appearing in at least one configuration in CB ′ be the set of multisets {L , . . . , L } satisfying that, for all i, L ∈ Σ′ , and that • Let CW 1 i ∆ ∃ℓ1 ∈ L1 , . . . , ℓ∆ ∈ L∆ such that {ℓ1 , . . . , ℓ∆ } ∈ CW . It is easy to observe that, for all 2-separated problems, R R(Π) = Π, where we say that two problems are equal if they are the same problem up to label renaming.

Observation 4.1. Let Π = (Σ, ∆, δ, CW , CB ) be a 2-separated problem, and let Π′ = R(Π). Then, up to renaming of labels, Π′ = (Σ, δ, ∆, CB , CW ). ′ , C ′ ). Observe that the configurations present in C ′ Proof. Let us compute Π′ = (Σ′ , δ, ∆, CB W B are exactly the configurations {{ℓ1 }, . . . , {ℓδ }} such that {ℓ1 , . . . , ℓδ } ∈ CB , since the 2-separated property implies that, by adding any label to any other set, we obtain a configuration (of sets) where we could pick an invalid configuration (of the original problem). Hence, Σ′ = {{ℓ} | ℓ ∈ Σ}, ′ = C . Let us now compute C ′ . It contains exactly and by renaming {ℓ} to ℓ we obtain that CB B W ′ those configurations with labels from Σ that satisfy an existential quantifier. Since each set in Σ′ is ′ contains exactly those configurations {{ℓ }, . . . , {ℓ }} such that a singleton, this implies that CW 1 ∆ ′ =C . {ℓ1 , . . . , ℓ∆ } ∈ CW . Hence, by renaming {ℓ} to ℓ we obtain that CW W 2

While the assumptions regarding knowledge of global parameters such as n and ∆ may seem unnatural, they can only strengthen our lower-bound results.

White and black algorithms. Let Π = (Σ, ∆, δ, CW , CB ) be a problem in the black-white formalism. Throughout the paper, we will only consider Π in the context of (∆, δ)-biregular graphs where nodes are 2-colored. We now define the notion of algorithms in this setting. Let white be the color of the nodes that need to satisfy the constraint CW , and let black be the color of the nodes that need to satisfy the constraint CB . A T -round algorithm A for Π is a function that takes as input the T -radius neighborhood of a white node (which has degree ∆) and produces an output for each of its incident edges. We say that white nodes are active and black nodes are passive, in the sense that white nodes are the ones actually producing the outputs. ′ , C ′ ) is now a mapping from the neighborObserve that an algorithm for R(Π) = (Σ′ , δ, ∆, CB W ′ (which have degree δ) to outputs. In other words, the hoods of the nodes that need to satisfy CB roles of active and passive are now swapped. As a simple explanatory case, consider the setting where white nodes have degree ∆ and black nodes have degree 2. The round elimination statement described in the introduction essentially says that, if there is a T -round algorithm for Π where nodes of degree ∆ produce the outputs, then there is a (T − 1)-round algorithm for R(Π) where nodes of degree 2 produce the outputs. Computable vs non-computable algorithms. We previously said that a T -round algorithm A for Π is a function f that takes as input the T -radius neighborhood of a white node (which has degree ∆) and produces an output for each of its incident edges. Note that we did not require f to be a computable function. In fact, we allow it to be non-computable (though we require it to be measurable), and our lower bounds hold even in the setting where we allow non-computable algorithms (and hence they are stronger lower bounds). We will exploit non-computability when defining an algorithm for R(Π): if we allow an unbounded number of random bits for each node, the algorithm that we define may not be computable. However, it does not matter, since the final result is a lower bound that holds even for non-computable algorithms, and hence for computable ones as well.

Automatic Self Reduction

In this section, we prove the following theorem. Theorem 5.1. Let Π be a b-dominant 2-separated problem. Let ε0 be a lower bound on the expected error of any 0-round algorithm for Π that has 0 white error. Let G be a family of (∆, δ)-biregular graphs of girth at least c log∆ n, for some constant c > 0. W.l.o.g., assume ∆ ≥ δ. Then, any algorithm for Π on G with 0 white error and at most ε expected error requires c′ min log∆ n, log2+b ε0 /ε rounds in the randomized LOCAL model, where c′ > 0 depends only on c. We will obtain Theorem 5.1 by a recursive application of the following statement. Lemma 5.2. Let Π = (Σ, ∆, δ, CW , CB ) be a 2-separated b-dominant problem. Assume Π can be solved in T ≥ 1 rounds with expected error at most ε and white error 0 in graphs with girth at least 2T + 3. Then, Π′ = R(Π) can be solved in T − 1 rounds with expected error at most 16(1 + b)ε and black error 0. We first show that Lemma 5.2 implies Theorem 5.1. Then, we prove Lemma 5.2. Proof of Theorem 5.1. Let G be any (∆, δ)-biregular 2-colored graph of girth Ω(log∆ n). Assume there exists a T -round algorithm for Π with expected error ε, white error 0, and T sufficiently 12

small compared to the girth. Let S = 2⌈T /2⌉. Then, by applying Lemma 5.2 we obtain that there exists a (S − 1)-round algorithm for R(Π) with expected error at most 16(1 + b)ε and black error 0. By repeating the same argument for S times, we obtain that there exists a 0-round S algorithm for RS (Π) with expected error at most 16(1 + b) ε and white error 0. By applying Observation 4.1, we get that R R(Π) = Π, and hence there exists a 0-round algorithm for Π with S S expected error at most 16(1 + b) ε. By assumption, we know that 16(1 + b) ε ≥ ε0 . Hence, S ≥ log16(1+b) εε0 ∈ Ω log2+b εε0 , which implies the same asymptotic bound for T , and the claim follows. The rest of the section is devoted to proving Lemma 5.2.

5.1

The Faster Algorithm

We define a (T − 1)-round algorithm A′ for solving R(Π) as a function of a given T -round algorithm A for Π. Let v be a black node. We define the output of v solely as a function of its (T − 1)-radius neighborhood BT −1 (v). Node v, for each neighboring white node u, considers all possible extensions of BT −1 (v) ∩ BT (u) into T -radius neighborhoods of u (that is, all possible random bits assignments for the nodes that are at distance T from v and T − 1 from u, and all the nodes that are at distance T + 1 from v and T from u). For each such extension, it computes the output of A on u. For each possible output ℓ, we obtain a probability pℓ that u outputs ℓ on the edge {u, v}. Observe that, while we provided an algorithmic description, pℓ is just Pr[Node u outputs ℓ towards v | BT −1 (v)]. Let pi,ℓ be the value obtained for label ℓ on the ith incident edge of v (that we simply call port i). We define the discrepancy of a label ℓ on portPi as D(i, ℓ) = 1− pi,ℓ , and we define the discrepancy of a configuration C = (ℓ1 , . . . , ℓδ ) as D(C) = 1≤i≤δ D(i, ℓi ). Observe that the discrepancy of a configuration C is the expected number of ports in which A outputs a label that is not the one specified by C. Note that now the order of the labels in the configuration matters (the discrepancy depends on which port gets which label). In this section, we will need to compute the distance between two configurations, in a setting where the order matters. Hence, we extend the definition of distance to this setting. For two tuples C1 and C2 , we define their distance d(C1 , C2 ) as the number of positions in which they differ. Moreover, unless otherwise specified, each constraint will now be seen as a set of tuples (e.g., if CW = {{2, 1, 1}}, we now consider it as CW = {(2, 1, 1), (1, 2, 1), (1, 1, 2)}). We define A′ as the algorithm that, among all configurations in CB , outputs the configuration C (seen now as a tuple of size δ and not just as a multiset, because the order matters) that minimizes the discrepancy D(C). Recall that, by Observation 4.1, up to renaming of labels, R(Π) = (Σ, δ, ∆, CB , CW ). Hence, the defined algorithm A′ never produces an invalid configuration on the black nodes, and we will later upper bound its white error as a function of the black error of A. As a side note, the standard black-box lifting theorem of round elimination defines A′ very differently: it first computes pi,ℓ for each i and ℓ as in our case, but then it takes some fixed threshold f and on each port i it outputs the set containing all the labels ℓ satisfying pi,ℓ ≥ f . The threshold f is then chosen to minimize the sum of the failure probabilities of the black and the white nodes. Note that such an algorithm could fail on both black and white nodes.

5.2

A Simpler Statement

Before proving Lemma 5.2, we provide a simpler statement that has a simpler proof. In some sense, we now give the best bound that we can prove if we only exploit 2-separation (and we do not use dominance). We will bound the error of A′ in terms of its discrepancy. We prove a bound on the

discrepancy of each node v, as a function of the error produced by A on v. Later, we will improve the bound and make it depend on b, and we will obtain Lemma 5.2 by essentially going through all nodes and all possible random bits assignments. Let X be the random variable denoting the output of A on the edges incident to v, conditioned on a fixed BT −1 (v). Note that X is a random variable that depends on the random bits seen by the neighbors of v (in T rounds) and not seen by v itself (in T −1 rounds). Let εv = E[d(X, CB ) | BT −1 (v)]. In other words, εv is the expected error that A produces on v, conditioned on a fixed (T − 1)neighborhood of v. Let Cv be the output of A′ on v. Let dv = D(Cv ) be its discrepancy. Lemma 5.3. Let v be a black node. Then, dv ≤ 2δεv . Proof. For a configuration C = (ℓ1 , . . . , ℓδ ), let Pr[C] be the probability that the original algorithm A outputs C on the edges incident to v, conditioned on the fixed (T − 1)-neighborhood of v, BT −1 (v). By the assumption on T and the girth, we have that for each pair of neighbors u1 and u2 of Qv, it holds that BT (u1 ) \ BT −1 (v) ∩ BT (u2 ) \ BT −1 (v) = ∅. Hence, by independence, Pr[C] = 1≤i≤δ pi,ℓi . In order to provide an upper bound on dv , we consider the following quantity: X Pr[C]D(C). C∈CB

That is, for each valid black configuration, we sum its probability, weighted by its discrepancy. Let qv be the probability that A produces an invalid configuration on v, conditioned on BT −1 (v). Since Cv minimizes the discrepancy, we obtain the following lower bound: X X X Pr[C]D(C) ≥ Pr[C]D(Cv ) = dv Pr[C] = (1 − qv )dv . C∈CB

C∈CB

In order to provide an upper bound, we first define the invalid neighborhood of a valid configuration C w.r.t. position i, as follows. Let C = (ℓ1 , . . . , ℓδ ) ∈ CB be a valid configuration. Ni (C) is the set of configurations that in all positions j = ̸ i have label ℓj , and in position i have a label different from ℓi . By the 2-separated property, all configurations in Ni (C) are invalid, because they differ from C in exactly 1 position. Observe that, for any configuration C = (ℓ1 , . . . , ℓδ ) ∈ CB , and all 1 ≤ i ≤ δ, the following holds: X Pr[C] (1 − pi,ℓi ) ≤ p1,ℓ1 · . . . · pi−1,ℓi−1 · (1 − pi,ℓi ) · pi+1,ℓi+1 · . . . · pδ,ℓδ = Pr[Z]. Z∈Ni (C)

Hence, we obtain the following upper bound: X X X X X Pr[C]D(C) = Pr[C] (1 − pi,ℓi ) ≤ C∈CB

Pr[Z].

C∈CB 1≤i≤δ Z∈Ni (C)

C=(ℓ1 ,...,ℓδ )∈CB 1≤i≤δ

We claim that for each possible Z, we sum Pr[Z] at most δ times. In fact, for each Z for which we sum Pr[Z], we must obtain Z by picking some C ∈ CB , then we must pick a position 1 ≤ i ≤ δ, then we must change the label of C in position i and obtain Z. We claim that there are at most δ choices (C, i) that give Z: first, for each C, there cannot be two values i, j such that Z ∈ Ni (C) and Z ∈ Nj (C), because Z differs from C in exactly one position. Then, for each position i, there exists at most one C such that Z ∈ Ni (C), because otherwise there would be two configurations C1 , C2 ∈ CB that, by changing them in a single place, we obtain Z, which would imply that 14

d(C1 , C2 ) = 1. By the 2-separated property, this is not possible. Since there are δ possible positions, we obtain that, for each Z, we sum Pr[Z] for at most δ times. P Moreover, each Z for which we sum Pr[Z] is a configuration not in CB , and we know that Z ∈C / B Pr[Z] = qv . Hence, X X X Pr[Z] ≤ δqv . C∈CB 1≤i≤δ Z∈Ni (C)

Summarizing, we obtained the following, (1 − qv )dv ≤

Pr[C]D(C) ≤ δqv .

C∈CB

Also, trivially, dv ≤ δ. If qv < 1, we get the following: dv ≤ δqv /(1 − qv ), and hence: dv ≤ min {δ, δqv /(1 − qv )} ≤ 2δqv . Note that, whenever the original algorithm produces an error on a node, in order to obtain a correct configuration on the node it is required to change at least one label. Hence, qv ≤ εv , and the claim follows. Note that the conclusion trivially holds also if qv = 1.

5.3

An Improved Bound that Depends on b

We devote this subsection to proving the following lemma. Lemma 5.4. Let v be a black node. Then, dv ≤ 16(b + 1)εv . We define the set of dominant labels as D = {ℓ | ∃C ∈ CB s.t. mC (ℓ) ≥ δ − b}, that is, all labels for which there exists at least one valid configuration containing it for at least δ − b times. The proof is structured as follows. We first prove that the output of A does not deviate too much from {ℓ, . . . , ℓ} for some fixed ℓ. Then, we consider the simple case in which δ is small compared to b (and we simply conclude the proof by applying Lemma 5.3), and then, for the case in which δ is large compared to b, we consider separately the cases ℓ ∈ / D and ℓ ∈ D. The output of A is not too far from {ℓ, . . . , ℓ} for some ℓ. Let Dℓ = D (ℓ, . . . , ℓ) , that is, the discrepancy of the (possibly invalid) configuration using only label ℓ. We prove that there exists some label ℓ∗ satisfying Dℓ∗ ≤ 2(εv + b) + 1. In other words, if we sum the probabilities of not obtaining ℓ∗ , we get at most 2(εv + b) + 1. Lemma 5.5. There exists a label ℓ∗ satisfying Dℓ∗ ≤ 2(εv + b) + 1. Proof. Recall that X is the random output of A conditioned on BT −1 (v). Let Xi be the random variable denoting the output of A on port i of v, conditioned on BT −1 (v). Let dD (C) = minℓ∈D d C, (ℓ, . . . , ℓ) , that is, the minimum distance from C to a configuration using a single dominant label. We start asking, for how many pairs (i, j) where i ̸= j, algorithm A produces an output where Xi ̸= Xj , in expectation. The following holds:   X 1{Xi ̸=Xj }  ≤ E δ(δ − 1) − δ − dD (X) δ − dD (X) − 1 ≤ E[2δdD (X)], E i̸=j

where the first inequality provides an upper bound as follows. Let ℓ be the label from D that appears in (the realization of) X the most. It appears δ − dD (X) times. Then, the number of different pairs is at most the number of pairs different from (ℓ, ℓ). Observe that dD (C) ≤ d(C, CB ) + b, because C is within distance d(C, CB ) from a valid configuration, and any valid configuration contains some dominant label at least δ − b times by the b-dominant property. Similarly, E[dD (X)] ≤ εv + b, because X has expected error εv , and hence expected distance εv from a valid configuration. We thus get the following:   X E 

1≤i≤δ 1≤j≤δ, j̸=i

 1{Xi ̸=Xj }   ≤ 2δ(εv + b).

This means that there exists some i∗ such that: 



 X  E 1{Xi∗ ̸=Xj }    ≤ 2(εv + b). 1≤j≤δ, j̸=i∗

This implies the following:   X X X  X  = ∗ ̸= Xj ] = ∗ ,ℓ E 1 Pr[X p (1 − pj,ℓ ) ≤ 2(εv + b). i i {X = ̸ X } ∗ j i   1≤j≤δ, j̸=i∗

1≤j≤δ, j̸=i∗

ℓ∈Σ

1≤j≤δ j̸=i∗

This implies that there exists some ℓ∗ satisfying: X (1 − pj,ℓ∗ ) ≤ 2(εv + b). 1≤j≤δ j̸=i∗

Since 1 − pi∗ ,ℓ∗ ≤ 1, we thus get: Dℓ∗ =

(1 − pj,ℓ∗ ) ≤ 2(εv + b) + 1.

1≤j≤δ

The case δ < 8(b + 1). We start by considering a simple case, that is, δ < 8(b + 1). In this case, by applying Lemma 5.3, we get dv ≤ 2δεv ≤ 16(b + 1)εv , concluding the proof. Hence, in the following, assume δ ≥ 8(b + 1). The case ℓ∗ ∈ / D. Assume ℓ∗ ∈ / D. On a high level, we now know that A produces an output that, in expectation, is not far from {ℓ∗ , . . . , ℓ∗ } and ℓ∗ is not a dominant label, but any valid configuration contains some ℓ = ̸ ℓ∗ for at least δ − b times. This implies that A produces a large error as a function of δ, and in order for this to not be a contradiction we get that δ is small (i.e., linear in εv + b + 1).

More formally, observe that, for any ℓ ∈ D, d {ℓ, . . . , ℓ}, {ℓ∗ , . . . , ℓ∗ } = δ. Hence, for any configuration C, dD (C) + d C, {ℓ∗ , . . . , ℓ∗ } ≥ δ. This implies the following: δ ≤ E[dD (X)] + E d X, {ℓ∗ , . . . , ℓ∗ } ≤ εv + b + Dℓ∗ ≤ εv + b + 2(εv + b) + 1 = 3εv + 3b + 1. We now conclude the proof with a simple case analysis. Suppose εv ≥ 1/4. Then, dv ≤ δ ≤ 3εv + 3b + 1 ≤ 3εv + 3b + 4εv = 7εv + 3b ≤ 12(b + 1)εv , concluding the proof. Hence, assume εv < 1/4. This case does not apply, since 8(b + 1) ≤ δ ≤ 3εv + 3b + 1 < 3/4 + 3b + 1 gives a contradiction. The case ℓ∗ ∈ D. If εv ≥ 1/4, then the discrepancy dv of A′ is at most the discrepancy of any configuration C ∈ CB satisfying mC (ℓ∗ ) ≥ δ − b, which exists by the assumption ℓ∗ ∈ D and the definition of D. This discrepancy is at most the discrepancy of {ℓ∗ , . . . , ℓ∗ }, which is Dℓ∗ , plus the distance from it to C. We thus get the following, dv ≤ Dℓ∗ + b ≤ 2(εv + b) + 1 + b = 2εv + 3b + 1 ≤ 2εv + 3b + 4εv ≤ 6εv + 3b ≤ 12(b + 1)εv , which concludes the proof. Hence, assume εv < 1/4. Observe that the following holds: 1 3 Dℓ∗ ≤ 2(εv + b) + 1 < 2 + b + 1 = 2b + . 4 2 Restricting to valid configurations dominated by ℓ∗ . Informally, we now restrict to the valid configurations that contain ℓ∗ for at least δ − b times, and, in such a setting, we prove an analogue of a statement proved in Lemma 5.3. Let Cℓ∗ = {C ∈ CB | mC (ℓ∗ ) ≥ δ − b}, that is, Cℓ∗ is the set of valid configurations that have ℓ∗ as dominant label. Let qℓ∗ = Pr[X ∈ / Cℓ∗ ]. Let dℓ∗ = minC∈Cℓ∗ E[d(C, X)]. In other words, consider the setting in which only the configurations in Cℓ∗ are valid. In such a setting, qℓ∗ is the probability that A fails, and dℓ∗ is the minimum discrepancy of A′ if it is restricted to output configurations from Cℓ∗ . Lemma 5.6. dℓ∗ ≤ (Dℓ∗ + b + 1) qℓ∗ / (1 − qℓ∗ ) . Proof. We consider the following quantity: X

Pr[C]D(C).

C∈Cℓ∗

Similarly as in the proof of Lemma 5.3, we lower bound this quantity as follows: X X Pr[C]D(C) ≥ dℓ∗ Pr[C] = (1 − qℓ∗ ) dℓ∗ . C∈Cℓ∗

C∈Cℓ∗

Similarly as in the proof of Lemma 5.3, for a configuration C = (ℓ1 , . . . , ℓδ ) ∈ Cℓ∗ , we define Ni (C) as the set of configurations that in all positions j ̸= i have label ℓj , and in position i have a label different from ℓi . By the 2-separated property, all configurations in Ni (C) are not in Cℓ∗ , because they differ from C in exactly 1 position, and Cℓ∗ ⊆ CB . Observe that, for any configuration C = (ℓ1 , . . . , ℓδ ) ∈ Cℓ∗ , and all 1 ≤ i ≤ δ, the following holds: X Pr[C] (1 − pi,ℓi ) = pi,ℓi · p1,ℓ1 · . . . · pi−1,ℓi−1 · (1 − pi,ℓi ) · pi+1,ℓi+1 · . . . · pδ,ℓδ = pi,ℓi Pr[Z], Z∈Ni (C)

which is similar to the bound used in Lemma 5.3, except that there we upper bounded pi,ℓi by 1. In Lemma 5.3, we continued by upper bounding (by δ) how many times we sum Pr[Z] for each Z. We now proceed similarly, except that now we perform a count that is weighted by pi,ℓi . Let C i→ℓ be the configuration obtained by replacing the ith label of C with ℓ. We obtain the following equality: X X X Pr[C]D(C) = Pr[C] (1 − pi,ℓi ) C∈Cℓ∗

C=(ℓ1 ,...,ℓδ )∈Cℓ∗ 1≤i≤δ

pi,ℓi

Pr[Z]

Z∈Ni (C)

pi,ℓi Pr[Z]

(C,i,Z) : C=(ℓ1 ,...,ℓδ )∈Cℓ∗ ∧ 1≤i≤δ ∧ Z∈Ni (C)

X Z ∈C / ℓ∗

Pr[Z]

pi,ℓi

(C,i) : C=(ℓ1 ,...,ℓδ )∈Cℓ∗ ∧ 1≤i≤δ ∧ Z∈Ni (C)

Pr[Z] · W (Z), where W (Z) =

Z ∈C / ℓ∗

pi,ℓ ,

(i,ℓ) : Z i→ℓ ∈Cℓ∗

where in the fourth equality we used the 2-separated property to infer that if Z ∈ Ni (C) then Z∈ / Cℓ∗ . We call W (Z) the weight of Z. In the proof of Lemma 5.3, we essentially upper bounded the weight of Z with δ, but we now provide a better bound. Note that ℓ cannot be equal to the ith label of Z, since Z ∈ / Cℓ∗ but Z i→ℓ ∈ Cℓ∗ . Hence, let Z = (ℓ1 , . . . , ℓδ ). We get that X W (Z) ≤ (1 − pi,ℓi ) = D(Z), 1≤i≤δ

that is, the weight of Z is upper bounded by its discrepancy, which can be upper bounded by the discrepancy of (ℓ∗ , . . . , ℓ∗ ), plus the distance of Z from (ℓ∗ , . . . , ℓ∗ ). Let k(Z) = |{i | ℓi ̸= ℓ∗ }|. We thus get the following: W (Z) ≤ Dℓ∗ + k(Z). Now observe that, if W (Z) > 0, then Z ∈ Ni (C) for some i and some C ∈ Cℓ∗ . Hence, by changing 1 label of Z we obtain a configuration in Cℓ∗ , and by changing at most b additional labels we reach {ℓ∗ , . . . , ℓ∗ }. Hence, if W (Z) > 0, we get that k(Z) ≤ b + 1. We obtain the following: X X X Pr[C]D(C) = Pr[Z] · W (Z) ≤ Pr[Z] (Dℓ∗ + b + 1) = (Dℓ∗ + b + 1) qℓ∗ . C∈Cℓ∗

Z ∈C / ℓ∗

Hence, (1 − qℓ∗ ) dℓ∗ ≤

Pr[C]D(C) ≤ (Dℓ∗ + b + 1) qℓ∗ ,

C∈Cℓ∗

as required.

Considering again all the valid configurations. We now bound qℓ∗ as a function of εv . Observe that, for each configuration C = (ℓ1 , . . . , ℓδ ) ∈ CB \ Cℓ∗ , it holds that k(C) = |{i | ℓi ̸= ℓ∗ }| ≥ δ − b, by the b-dominant property and the fact that C is valid but not in Cℓ∗ . Hence, any configuration Z such that b < k(Z) < δ − b is invalid. Hence, Pr[b < k(X) < δ − b] ≤ εv . Recall that δ ≥ 8(b + 1) and that Dℓ∗ < 2b + 32 . Assume that Pr[k(X) ≥ b + 1] > 0. We now prove that E[k(X) | k(X) ≥ b + 1] ≤ Dℓ∗ + b + 1. ∗ Define Yi to be the indicator variable of the event Pδ Pδ that Xi ̸= ℓ . The variables Y1 , . . . , Yδ are independent and P k(X) = i=1 Yi . Also, E[k(X)] = i=1 Pr[Yi = 1] = Dℓ∗ . For each i ∈ {1, . . . , δ}, define k−i (X) = j̸=i Yj . For an event A, let 1(A) be the indicator random variable for event A. By independence, E[k(X)1({k(X) ≥ b + 1})] =

δ X

Pr[Yi = 1] Pr[k−i (X) ≥ b].

i=1

Now, Pr[k−i (X) ≥ b] = Pr[k−i (X) ≥ b + 1] + Pr[k−i (X) = b]. Note that Pr[k−i (X) ≥ b + 1] ≤ Pr[k(X) ≥ b + 1]. Hence, E[k(X)1({k(X) ≥ b + 1})] ≤

δ X

Pr[Yi = 1] Pr[k(X) ≥ b + 1] +

i=1

δ X

Pr[Yi = 1] Pr[k−i (X) = b].

i=1

Note that δ X

Pr[Yi = 1] Pr[k−i (X) = b] =

i=1

δ X

Pr[Yi = 1, k(X) = b + 1]

i=1 δ X = E[ Yi 1({k(X) = b + 1})] i=1

= (b + 1) Pr[k(X) = b + 1] ≤ (b + 1) Pr[k(X) ≥ b + 1]. Therefore, E[k(X)1({k(X) ≥ b + 1})] ≤

δ X

! Pr[Yi = 1] + b + 1 Pr[k(X) ≥ b + 1]

i=1

= (Dℓ∗ + b + 1) Pr[k(X) ≥ b + 1]. Since by definition E[k(X) | k(X) ≥ b + 1] =

E[k(X)1({k(X) ≥ b + 1})] , Pr[k(X) ≥ b + 1]

dividing both sides of the previous inequality by Pr[k(X) ≥ b + 1] gives the desired claim.

Now assume Pr[k(X) ≥ b + 1] = 0. Then Pr[k(X) ≥ δ − b] = 0 ≤ εv , so the desired bound holds trivially. Otherwise, by Markov’s inequality under the conditional distribution given k(X) ≥ b + 1, we get the following: Pr[k(X) ≥ δ − b] Pr[k(X) ≥ δ − b ∧ k(X) ≥ b + 1] = = Pr[k(X) ≥ δ − b | k(X) ≥ b + 1] Pr[k(X) ≥ b + 1] Pr[k(X) ≥ b + 1] 3b + 25 3b + 52 Dℓ∗ + b + 1 1 ≤ ≤ ≤ ≤ . δ−b δ−b 7b + 8 2 Hence, 2 Pr[k(X) ≥ δ − b] ≤ Pr[k(X) ≥ b + 1] = Pr[b < k(X) < δ − b] + Pr[k(X) ≥ δ − b]. This implies Pr[k(X) ≥ δ − b] ≤ Pr[b < k(X) < δ − b] ≤ εv . We get that 1 qℓ∗ ≤ Pr[X ∈ / CB ] + Pr[k(X) ≥ δ − b] ≤ 2εv < . 2 Finally, (Dℓ∗ + b + 1) qℓ∗ ≤ 2 (Dℓ∗ + b + 1) qℓ∗ 1 − qℓ∗ ≤ 4 (Dℓ∗ + b + 1) εv ≤ 4 (2b + 2) + b + 1 εv = 12(b + 1)εv ,

dv ≤ dℓ∗ ≤

concluding the proof.

5.4

Proof of Lemma 5.2.

The proof is essentially obtained by summing the bound of Lemma 5.4 over all nodes, and considering all possible random bits assignments. In order to prove this statement, we upper bound the error of the algorithm A′ that we previously defined. In order to bound the error of A′ , we bound its expected deviation from the output of A, that is, in expectation, on how many edges A′ produces an output that is not exactly the same as the output produced by A. Suppose the expected deviation is d. Then, we can upper bound the error of A′ as d because: • A′ has 0 black error. • Given an output of A′ , in expectation we need to change d labels to obtain the output of A. But A has 0 white error, and hence we need to change d labels in expectation to produce a solution with 0 white error. • The error of A′ is the sum, over all black nodes and all white nodes, of how many labels we need to change at most to make the node happy. We hence have that the black error is 0 and the expected white error is upper bounded by d. Hence,P the claim follows if we Pprove that d ≤ 16(b + 1)ε. Let B be the set of black nodes. Observe that E v∈B εv ≤ ε, and E v∈B dv = d, where the expectation is taken over all possible random bit assignments to the nodes. Hence, by Lemma 5.4 and linearity of expectation, " # " # X X d=E dv ≤ 16(b + 1)E εv ≤ 16(b + 1)ε. v∈B

v∈B

Hence, the claim follows. 20

Applications

In this section, we provide some applications of Theorem 5.1. We will exploit the following high-girth graph construction, for which we provide an explicit proof for the exact parameter range we need. Lemma 6.1. There exist three positive constants α, ∆0 , and ε such that, for every sufficiently large n and every ∆ satisfying that n∆ is even and that ∆0 ≤ ∆ ≤ n1/4 , there exists a ∆-regular graph ∆ on n nodes that has girth at least ε log∆ n and independence number at most α n log ∆ . Proof sketch. The first part of the main theorem of Frieze and Luczak [FL92] implies that, for every sufficiently large n and every ∆0 ≤ ∆ ≤ n1/4 with n∆ even, a uniformly random simple ∆-regular graph on n nodes has independence number at most O(n log ∆/∆) with high probability. Fix a sufficiently small auxiliary constant η > 0. If η log∆ n < 4, the graph is simple and hence has girth at least 3 > η2 log∆ n. Thus, this case is already covered by taking ε = η/2. Otherwise, for g = ⌊η log∆ n⌋, the condition (∆ − 1)2g−1 = o(n) of McKay, Wormald, and Wysocka [MWW04] is satisfied. Lemma 1 of their paper, together with the Poisson means defined in their equation (1.2), implies that such a graph has at most O(n4η ) cycles of length less than g, with high probability. Hence, there exists a ∆-regular graph satisfying both properties simultaneously. Following the degree-preserving switching used in the proof of Lemma 2.1 of Alon [Alo10], we remove all its short cycles. The switchings preserve regularity and can be chosen so that they create no new short cycles. Since every switching removes only two edges, after O(n4η ) switchings the independence number has increased by at most O(n4η ). For a sufficiently small choice of η, this is o(n log ∆/∆), so the resulting graph has the claimed girth and independence number after adjusting the constants. The full argument is given in the appendix (see Lemma A.1). On a high level, all our results are obtained by applying the following idea, which is a direct application of Theorem 5.1. Observation 6.2. Let ΠL be a problem, and ΠG be a problem in the black-white formalism. Suppose that ΠG is 2-separated and b-dominant, and suppose that any 0-round algorithm for ΠG that has 0 white error has expected black error at least ε0 . Let G be a family of (∆, δ)-biregular graphs of girth Ω(log∆ n), and assume, w.l.o.g., that ∆ ≥ δ. Suppose that, on G, there is a T -round algorithm mapping a solution of ΠL into a solution of ΠG , such that the expected black error is at most ε and the white error is 0. Then, ΠL , on G, requires Ω min log∆ n, log2+b εε0 − T rounds. In other words, by exploiting Theorem 5.1, we can directly prove lower bounds for local problems, by exploiting a black-box lower bound that we obtain for global problems. Essentially, the lower bound that we obtain is the logarithm of the ratio ε0 /ε that we introduce in the mapping. For example, a lower bound for maximal matching immediately derives from the following observations: • Let ΠL be the problem of maximal matching. • Let ΠG be the problem of perfect matching. It is 2-separated and 1-dominant. • By Lemma 6.1, there are families of graphs of girth Ω(log∆ n) and independence number O(n log ∆/∆). If we solve ΠL in these graphs, unmatched nodes form an independent set, and hence they are at most O(n log ∆/∆). • Any 0-round algorithm for ΠG produces Ω(n) errors in expectation. • Consider the following mapping from ΠL to ΠG : unmatched nodes mark an arbitrary incident edge as matched. This produces O(n log ∆/∆) errors. 21

• We get that log εε0 ∈ Ω(log ∆). Hence, in order to prove a lower bound, it is sufficient to find a suitable pair (ΠL , ΠG ) of problems. We now provide some applications of this idea. An easy application of our new black-box lifting theorem is a lower bound for maximal k1 -integral matching, which is the problem of computing an assignment from {0, k1 , k2 , . . . , 1} to each edge, such that the values assigned to the edges incident to a node sum to at most 1, and no edge can be increased. 1 Theorem 2.11. Let k be a positive integer fixed independently of ∆ and n. Maximal k -integral √ matching requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized LOCAL model, for any algorithm with failure probability at most 1/n. These lower bounds hold even on ∆-regular graphs of girth Ω(log∆ n).

Proof. We consider the setting in which ∆ > k. Let ΠL be the maximal k1 -integral matching problem. Let ΠG be the perfect k1 -integral matching problem, that is, the problem of outputting a fraction from {0, k1 , k2 , . . . , 1} on each edge, such that, for each node, the sum of the values assigned to its incident edges is exactly 1. We call unsaturated nodes the nodes for which their edges do not sum to exactly 1. We claim that ΠG is 2-separated and (k + 1)-dominant. Its edge constraint contains all pairs { ki , ki } for 0 ≤ i ≤ k, which clearly satisfies 2-separation (and trivially it is 2-dominant, and 2 ≤ k+1). Its node constraint contains all multisets of size ∆ where each label is from {0, k1 , k2 , . . . , 1} and the sum is exactly 1. Observe that k-dominance is satisfied: each configuration C must satisfy mC (0) ≥ ∆ − k. Now, suppose for a contradiction that the node constraint is not 2-separated. This means that there exist two P configurationsPC1 = {ℓ1 , . . . , ℓ∆ } and C2 = {ℓ′1 , . . . , ℓ′∆ } that satisfy d(C1 , C2 ) = 1. This means 1≤i≤∆ ℓi ̸= 1≤i≤∆ ℓ′i , and hence that at least one of the two configurations does not sum to 1, a contradiction. Consider the family of graphs from Lemma 6.1. In such graphs, the independence number is O(n log ∆/∆). In any solution for ΠL , it must hold that unsaturated nodes form an independent set: for a contradiction, suppose u and v are neighboring unsaturated nodes; we could increase the edge between them by at least 1/k, contradicting maximality. Consider the following mapping from ΠL to ΠG : each unsaturated node v picks an arbitrary node-edge pair labeled 0 and increases it such that v becomes saturated. We obtain a solution for ΠG in which there are no errors on the nodes, and O(n log ∆/∆) errors on the edges, because there are O(n log ∆/∆) unsaturated nodes, and each of them modifies a single edge. Now consider an arbitrary 0-round algorithm for ΠG with 0 white error. Any 0-round algorithm must produce an output solely as a function of the random bits it sees on the node. On each node, since ∆ > k, and since it must output labels that sum to 1, it must output 0 on at least one edge, and non-0 on at least one edge. This implies that, if we look at an arbitrary edge, we get that it must get different labels with probability at least 1/∆. Since the number of edges is n∆/2, we get that error is Ω(n). Hence, the claim follows by applying Observation 6.2 (and the √ √ the expected Ω log n lower bound is obtained by picking ∆ = 2 log n ). We now consider the maximal H-packing problem, where the goal is to find a maximal collection of vertex-disjoint copies of H in the input graph, where H is a fixed tree. In the following, we assume that the degree of H is strictly less than the degree of G (or, in other words, in order to prove our lower bound, we consider a family of graphs with sufficiently large degree). Theorem 2.12. Let H be a tree with at least 2 nodes fixed independently of ∆ and n. The maximal √ H-packing problem requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized 22

LOCAL model, for any algorithm with failure probability at most 1/n. These lower bounds hold even on ∆-regular graphs of girth Ω(log∆ n). Proof. Let ΠL be the maximal H-packing problem. Let Π be the perfect H-packing problem, that is, maximal H-packing restricted to solutions in which each node is in a copy of H. We prove that there exists a problem ΠG in the black-white formalism that is 2-separated and OH (1)-dominant, and such that, given a solution to Π, we can solve ΠG in OH (1) rounds, where OH (1) hides the dependencies on H. We define a labeling ℓ : VH × EH → Σ for some finite set Σ of labels to be defined later. Consider the incidence graph H ′ = (VH ′ , EH ′ ) of H, that is, the graph where there is a white node for each node in VH and a black node for each edge in EH , connected in the natural way. Let c ∈ VH ′ be the node with minimum eccentricity in H ′ (note that this node is unique). For each node v ∈ VH ′ , let p(v) be the edge on the shortest path from v to c, and let p(c) be undefined. For each node v = ̸ c, let t(v) be the subtree rooted at v and induced by the nodes reachable from v by not using the edge p(v). Let T = {t(v) | v ∈ VH ′ \ {c}} be the set of subtrees appearing in H ′ , where two trees are considered equal if they are equal up to isomorphism (where the isomorphism preserves the root and the colors of the nodes). Let σ be an arbitrary bijective function from T to {1, . . . , |T |}. In other words, σ assigns a unique integer to each possible type of subtree. For each edge e = {u, v}, let u be the node satisfying p(u) = e. We label e with σ(t(u)). Then, we map back this labeling to H in the natural way (and Σ is the set of labels that we used). We define ΠG as follows. The set of labels is Σ ∪ {⊥}. If H contains an edge labeled {ℓ, ℓ′ }, we allow the edge configuration {ℓ, ℓ′ }. Moreover, we allow the edge configuration {⊥, ⊥}. If H contains a node labeled {ℓ1 , . . . , ℓd }, we allow the node configuration {ℓ1 , . . . , ℓd , ⊥, . . . , ⊥} of size ∆. Figure 2 gives an example of this encoding. We claim that ΠG is 2-separated and OH (1)-dominant. We first handle the configuration at the center c. Let r be the radius of H ′ . Since c is its unique center, at least 2 subtrees rooted at children of c have height exactly r − 1, while all subtrees rooted at distance ≥ 2 from c have height ≤ r − 2. If c is black, it has exactly two children, and both corresponding subtree types occur only at children of c. Hence, both labels in the edge configuration of c occur in no other edge configuration, so its distance from every other edge configuration is 2. Similarly, if c is white, its node configuration contains at least two labels (possibly the same twice) that occur in no other node configuration. In either case, its configuration has distance at least two from every other configuration of the same constraint. We can thus restrict the remaining argument to configurations arising at nodes other than c. Suppose for a contradiction that 2-separation does not hold on the edge constraint. Then there exist two allowed configurations {ℓ, ℓ1 } and {ℓ, ℓ2 }. This implies that there exist two subtrees t1 and t2 of type ℓ such that, if we connect a black node to the root of t1 we obtain a different tree from the one obtained by adding a black node to the root of t2 , which is a contradiction, because t1 = t2 . Now consider the node configurations. Suppose there exist two configurations C1 and C2 such that d(C1 , C2 ) = 1. From C1 and C2 we extract the two trees from which they have been constructed, t1 and t2 . They must have different types, ℓ1 and ℓ2 . Consider two cases, either the roots of t1 and t2 have the same degree, or not. In the former case, since t1 and t2 have different types but same degree, this implies that the types of the children of the roots of t1 and t2 differ. Hence, there are at least two differences between C1 and C2 , the label of the root and the label of the child. In the latter case, C1 and C2 are of the following form. C1 = {ℓ1 , . . . , ℓd , ⊥, . . . , ⊥} and C2 = {ℓ′1 , . . . , ℓ′d′ , ⊥, . . . , ⊥} with d = ̸ d′ , w.l.o.g. d < d′ . Moreover, it cannot hold that {ℓ1 , . . . , ℓd } ⊂ {ℓ′1 , . . . , ℓ′d′ }, since this would require σ to assign the same label to a tree rooted at a black node and to a tree rooted at a white node. Hence, there are at least two differences. Consider an arbitrary solution of ΠL , and let U be the subgraph induced by nodes that are not 23

σ(t) = 1

σ(t) = 2

σ(t) = 3

σ(t) = 4

(a) The four rooted subtree types; a blue ring marks each root.

4 2 4

4 2 4 3

2 2 1

3 2 2

2 2 1

(b) The incidence graph H ′ , rooted at its center c.

2 2 1

Σ = {1, 2, 3, 4, ⊥}, CW = {4, 4, 2, ⊥}, {3, 2, 2, ⊥}, {1, ⊥, ⊥, ⊥} , CB = {4, 3}, {2, 1}, {⊥, ⊥} . Figure 2: Encoding perfect H-packing for an eight-node tree H that contains the same subtree multiple times. In (b), each edge is labeled by the type of the subtree below it. Types 3 and 4 each occur twice, while types 1 and 2 each occur five times, including along the short middle branch. The constraints below the diagrams are for perfect H-packing in a 4-regular input graph. Edges outside the copies of H receive ⊥ at both endpoints.

part of any copy of H. We prove that U can be colored with OH (1) colors. Let h = |V (H)|. By maximality, U contains no copy of H. Every graph of minimum degree at least h − 1 has at least h vertices and contains every h-vertex tree as a subgraph, by greedy embedding. Thus, no subgraph of U has minimum degree at least h − 1, so U is (h − 2)-degenerate and hence (h − 1)-colorable. Consider the family of graphs from Lemma 6.1. In such graphs, the independence number is O(n log ∆/∆). Hence, any subset of nodes that is OH (1) colorable includes at most a fraction O(log ∆/∆) of the nodes. Consider the following mapping from ΠL to ΠG : nodes that are part of some H spend OH (1) rounds to compute their labeling in H, and output the associated configuration. Nodes not in H output the configuration that a leaf of H would output, in an arbitrary way. We obtain a solution for ΠG in which there are no errors on the nodes, and O(n log ∆/∆) errors on the edges, because there are O(n log ∆/∆) nodes that are not part of any H, and each of them can create at most one edge error (on the edge not getting ⊥). Now consider an arbitrary 0-round algorithm for ΠG . Any 0-round algorithm must produce an output solely as a function of the random bits it sees on the node. Observe that each valid node configuration contains at least two labels (⊥ and something else), and each label is edge compatible only with a single other label. Hence, an edge gets an error with probability at least 1/∆, and thus error is Ω(n). Hence, the claim follows by applying Observation 6.2 (and the √ √ the expected Ω log n lower bound is obtained by picking ∆ = 2 log n ). We now consider the bipartite maximal matching problem. While a lower bound of Ω(log ∆) is already known for maximal matching, we now show that it can be extended to bipartite 2-colored graphs. For this purpose, we first prove the following statement. Lemma 6.3. For every sufficiently large even n and every 3 ≤ ∆ ≤ n1/4 , there exists a bipartite ∆-regular graph on n nodes of girth Ω(log∆ n) in which every maximal matching leaves at most an O(log ∆/∆) fraction of the nodes unmatched. The proof of this lemma is deferred to the appendix. See Lemma A.2. It is similar to that of Lemma A.1; however, since we need to focus on bipartite graphs, we need to change the random graph model of interest, and we consider the bipartite configuration model. Theorem 2.13. The maximal matching problem, on bipartite ∆-regular 2-colored graphs of girth √ Ω(log∆ n), requires Ω (min {log∆ n, log ∆}) rounds and Ω log n rounds in the randomized LOCAL model, for any algorithm with failure probability at most 1/n. Proof. Consider the bipartite perfect matching problem. In the black-white formalism it can be expressed by using the constraints CW = CB = {{M, U, . . . , U}}. That is, each edge is either labeled M (matched) or U (unmatched), and each node needs to have exactly one M. Similarly as in the previous proofs, the error that we obtain when mapping bipartite maximal matching to perfect matching is O(n log ∆/∆), because there are O(n log ∆/∆) unmatched nodes, and again, any 0-round algorithm has Ω(n) expected error. Thus, the claim follows.

Optimality of Our Approach

We now discuss the optimality of our approach. Recall that, in order to upper bound the error of the faster algorithm, we provided an upper bound on the discrepancy of its output from the output of the original algorithm. We first show that, unless we change how we measure the error, 2-separation is somehow necessary to provide a good upper bound on the discrepancy. Let Π = (Σ, ∆, δ, CW , CB ). 25

If Π is not 2-separated, a valid black configuration of R(Π) is not necessarily composed of singletons, and in general it consists of nonempty label sets L1 , . . . , Lδ such that every choice ℓi ∈ Li gives a configuration {ℓ1 , . . . , ℓδ } ∈ CB . Given random labels X1 , . . . , Xδ , we define the discrepancy of this configuration, with Li assigned to port i, as D(L1 , . . . , Lδ ) =

δ X

Pr[Xi ∈ / Li ].

i=1

This is the expected number of ports on which the original output lies outside the chosen label set, and it agrees with our earlier definition when every Li is a singleton. We restrict to the case δ = 2. For any pair of sets A, B, we define their unordered product A ⊙ B as the set {{a, b} : a ∈ A, b ∈ B}, where the elements are multisets. Moreover, for two labels ℓ1 , ℓ2 we say that ℓ1 and ℓ2 are equivalent if, for any C ∈ CB , if we replace any number of occurrences of ℓ1 in C with ℓ2 , and any number of occurrences of ℓ2 in C with ℓ1 , we obtain a configuration C ′ ∈ CB . It is known that, if a problem Π uses equivalent labels, then Π can be normalized into an equivalent problem that does not use distinct equivalent labels. We show that, after this normalization, if the black constraint is not 2-separated, then some independent label distributions have expected error at most ε, while every valid choice of label sets √ has discrepancy Ω( ε). Consequently, the discrepancy cannot always be bounded by a constant multiple of the original expected error. In more detail, we prove the following theorem. Theorem 7.1. Let Π = (Σ, ∆, 2, CW , CB ) be a problem that does not contain distinct equivalent labels and whose black constraint is not 2-separated. Then, for every sufficiently small ε > 0, there exist probability distributions (pi,ℓ )ℓ∈Σ , one for each i ∈ {1, 2}, with the following property. Let X1 , X2 be independent random variables with Pr[Xi = ℓ] = pi,ℓ . Then E d {X1 , X2 }, CB ≤ ε, but, for every two non-empty subsets L1 , L2 ⊆ Σ such that L1 ⊙ L2 ⊆ CB , we have that √ D(L1 , L2 ) ≥ ε. Proof. Since CB is not 2-separated, there exist two configurations {x, z}, {y, z} ∈ CB such that x ̸= y. Also, since CB does not contain distinct equivalent labels, there exists a label w ∈ Σ such that, w.l.o.g., {x, w} ∈ CB and {y, w} ∈ / CB . Define ( √ x with probability 1 − ε; X1 = √ y with probability ε; ( √ z with probability 1 − ε; X2 = √ w with probability ε. The configuration (X1 , X2 ) is valid if and only if (X1 , X2 ) ̸= (y, w). Consider any pair of sets L1 , L2 ⊆ Σ such that L1 ⊙ L2 ⊆ CB . We cannot have that y ∈ L1 and w ∈ L2 , because otherwise {y, w} ∈ CB . Hence, either y ∈ / L1 , or w ∈ / L2 . If y ∈ / L1 , then √ Pr[X1 ∈ / L1 ] ≥ Pr[X1 = y] = ε. If, instead, w ∈ / L2 , then Pr[X2 ∈ / L2 ] ≥ Pr[X2 = w] = Hence, Pr[X1 ∈ / L1 ] + Pr[X2 ∈ / L2 ] ≥ proving the claim. 26

√

ε.

√

ε,

If we were able to prove a lower bound of Ω min log∆ n, log εε0 by exploiting only 2-separation, we would be able to obtain significantly more lower bounds for local problems. Unfortunately, 2-separation by itself is not sufficient. Theorem 2.15. There exists a problem Π that is 2-separated, not o(∆)-dominant, and that can be solved in T ∈ O 1 + log∆ εε0 rounds in the randomized LOCAL model in graphs of girth Ω(log∆ n) with target error at most ε, where ε0 ∈ Ω(n) is a lower bound on the expected error of any 0-round algorithm for the problem that has 0 white error, assuming ε is chosen such that T ∈ o(log∆ n). Proof. Consider the problem of computing an odd orientation, that is, an orientation of the edges such that all nodes have an odd number of outgoing edges, on ∆-regular graphs, where ∆ ≥ 4 is even. It can be encoded in the node-edge formalism by allowing the edge configuration {I, O}, that is, each edge is marked incoming by one endpoint and outgoing by the other, and by allowing all node configurations of size ∆ containing an odd number of O. Observe that the problem is 2-separated and (∆/2)-dominant, but any valid dominance parameter is at least ∆/2 − 1; hence it is not o(∆)-dominant. Observe that, since ∆ is even, each node must have at least one incoming and at least one outgoing edge. If both endpoints of an edge label the edge O, or they both label the edge I, this produces an error on the edge. Any 0-round algorithm must label edges without any coordination with the neighbors. This implies that each edge has an error with probability at least 1/2. Hence, the expected number of errors ε0 on the edges must be Ω(n). We give an algorithm that computes, on graphs of girth Ω(log∆ n), a solution in O 1 + log∆ εε0 rounds, where ε is the desired error. The algorithm proceeds as follows. Let T be a value to be fixed later. Each node samples itself with probability 1/(∆ − 1)T . Let S be the set of sampled nodes. We call these nodes centers. Each node spends 2T rounds to find the nearest node in S, if it exists. Consider the clustering obtained by putting each node in the cluster of its nearest center (breaking ties by assigning each center an independent uniform random priority from [0, 1] and choosing the center with the smallest priority), and by forming a singleton cluster if no center was found (and each singleton acts as the center of its own cluster). Orient inter-cluster edges arbitrarily. Then, in each cluster, brute force a solution where there is at most one error on one edge incident to the center (and no other error). Such a solution always exists, because we can process the nodes inwards, and make a node happy by picking the correct orientation for the edge towards the center. After this process, there can be at most one error on the center, which can fix itself by producing one edge error. This takes O(T ) rounds, since each cluster has radius at most 2T . Note that, for T small-enough compared with the girth of the graph, each node sees a tree. Hence, within 2T rounds, each node sees at least (∆ − 1)2T nodes. The probability that a node did not find a center within 2T rounds is at most: (∆−1)2T 1 1 T 1− ≤ e−(∆−1) ≤ . T (∆ − 1) (∆ − 1)T Hence, the expected error is at most the expected number of centers, plus the expected number Ω(T ) , and by picking of nodes that did not find a center within 2T rounds, which is at most n/∆ ε0 T ∈ Θ 1 + log∆ ε we obtain that the error is at most ε.

Open Questions

We now discuss possible future directions. In the following, we use p to denote ε/ε0 , and to simplify the explanation, we set aside possible differences between p and the standard failure probability. Alternatives to domination. In Section 6, we proved lower bounds for “local” problems ΠL , by finding suitable 2-separated O(1)-dominant problems ΠG that we can solve with small error, given a solution for ΠL . The reason why we required O(1)-domination is that, when performing the mapping from ΠL to ΠG we typically get an error in the ballpark of n/∆ (ignoring logarithmic factors). If we only had a lower bound of Ω(log∆ 1/p) for ΠG , we would not get any superconstant lower bound (i.e., Ω(log∆ ∆)). Hence, for this approach to work, it is crucial to have a lower bound of Ω(log 1/p) for ΠG (or at least a base of the logarithm that is subpolynomial in ∆). As shown in Theorem 2.15, 2-separation alone is not sufficient to improve the Ω(log∆ 1/p) lower bound to Ω(log 1/p). However, we do not know if O(1)-domination is necessary. We would like to understand if there are other types of restriction that we can use to obtain the improvement. Open Question 1. Which properties can be combined with 2-separation to obtain lower bounds that are strictly better than Ω(log∆ 1/p)? A concrete example. In order to make the question more concrete, we now describe a simple problem, that we call exact splitting, for which we do not know the exact complexity. Consider the problem of coloring the edges red and blue, such that each node has exactly ∆/2 edges of each color, in ∆-regular graphs where ∆ is even. This problem can be defined in the node-edge formalism as follows. The node constraint allows only C = {R, . . . , R, B, . . . , B}, where mC (R) = mC (B) = ∆/2. The edge constraint allows {R, R} and {B, B}. This problem is clearly 2-separated, but it is very far from being O(1)-dominant. However, this looks like a hard problem, for which we do not expect an O(log∆ 1/p) algorithm, but we do not know how to prove an ω(log∆ 1/p) lower bound with our current techniques. Open Question 2. What is the complexity of the exact splitting problem, as a function of p? Alternatives to separation. As shown in Theorem 7.1, 2-separation is necessary for our techniques to work. Nevertheless, we would like to understand whether we can obtain similar results for problems that are not 2-separated. For example, we know that there are problems for which an Ω(log∆ n) lower bound holds, but that are not 2-separated. An example of such a problem is the problem of orienting all edges such that all nodes have at least ∆ − 1 outgoing edges. Such a problem does not admit a solution in high-girth regular graphs, and this is known to imply an Ω(log∆ n) lower bound for ∆ ≥ 3, even on trees in which every node has degree either 1 or ∆, with leaves unconstrained. However, we do not know how to obtain such a lower bound directly via round elimination. Open Question 3. How can we obtain Ω(log∆ 1/p) lower bounds for problems that are not 2separated? MIS on regular high-girth graphs. A natural problem for which we cannot obtain a lower bound via our techniques is Maximal Independent Set on ∆-regular graphs of girth Ω(log∆ n). We know that obtaining a lower bound of Ω (min {log∆ n, log ∆}) is not possible, because there exists a better algorithm [KS26]. However, we would like to understand if a lower bound of Ω (min {log∆ n, log ∆/ log log ∆}) holds (which is the lower bound known in the non-regular case,

via KMW). We failed to find a problem ΠG that we can map to that is 2-separated and O(log ∆)dominant (which would suffice to obtain the lower bound). We would like to understand if such a reduction exists, or if we can find alternatives to separation or to domination that allow us to prove the required lower bound. Open Question 4. What is the complexity of MIS in regular high-girth graphs? Hard problems with large failure probability. The approach that we used in Section 6 suggests the following question: what is the complexity of “hard” problems, if we allow large failure probability? As shown, we can use hard problems that we cannot solve in o(log 1/p) to prove lower bounds for “local” problems. Typically, for problems studied in the LOCAL model, once we see that they are “global”, we do not investigate them much further. In our work, we show that it can still be very useful to determine their complexity as a function of the required failure probability. Partial results on this topic have been obtained: a recent work studied what is the best local failure probability one can achieve for 2-coloring cycles, if only 1 round of communication is allowed [FRS+26]. We suggest a systematic study of “hard” problems as a function of the required failure probability. Open Question 5. Let Π be a problem for which we know a deterministic Ω(log∆ n) lower bound. What is its complexity as a function of the required failure probability? Different notions of error. In order to achieve our results, we needed to introduce a new notion of error, that does not just look at whether a node fails or not, but it counts how many labels are wrong. There could be other notions of error that allow us to obtain even stronger lower bounds. For example, there could be other notions of error that give Ω(log 1/p) lower bounds without requiring 2-separation or O(1)-domination. In fact, we point out that, even assuming 2-separation and O(1)-domination, by using the standard notion of failure probability, we would have not been able to prove Ω(log 1/p) lower bounds. Open Question 6. Are there other measures of error that we can exploit in order to get automatic Ω(log 1/p) lower bounds? Direct round elimination lower bounds. While it is interesting that we can use the hardness of global problems to prove lower bounds for local problems, it would still be interesting to obtain direct lower bounds via round elimination. In more detail, consider the maximal matching problem. We know how to obtain a randomized lower bound of Ω (min {∆, log∆ log n}) via round elimination [BBH+21], and we know how to obtain a lower bound of Ω (min {log ∆, log∆ n}) if we first map a solution of maximal matching to perfect matching, and then we apply round elimination to perfect matching. However, we still do not know how to get the Ω (min {log ∆, log∆ n}) lower bound by applying round elimination directly to maximal matching. For this purpose, we would need to perform a better failure probability analysis for problems that are not 2-separated and, more fundamentally, are not even fixed points. Or, maybe, we would need to introduce a new form of round elimination that explicitly tracks the probability that a configuration is used. Open Question 7. Can we get an Ω (min {log ∆, log∆ n}) randomized lower bound for maximal matching, via a direct application of round elimination?

AI Methodology All the main ideas in the paper (the new measure of error, the new definition of the (T − 1)-round algorithm, the considered class of problems, and the applications) were discovered by humans. A preliminary version of the proof of Lemma 5.3 was discovered by humans, but LLMs (ChatGPT 5.6) were able to provide a simpler proof, which we then further simplified and used. LLMs then helped to extend the idea of Lemma 5.3 to the b-dominant case, although a similar idea had already appeared in [BCd+26, Lemma 3.8]. The paper was entirely written by humans; LLMs were used to fix typos, grammatical errors, small mathematical flaws, and to create figures.

Acknowledgments This work was partially supported by MUR, Fondo Italiano per la Scienza (FIS3), Award number: D53C25002470001: FIS-2024-03606 - A Robust Theory of Distributed Computation - CUP: D53C25002470001. Francesco d’Amore was supported by the project Decreto MUR n. 47/2025, CUP: D13C25000750001.

References [Alo10]

Noga Alon. “On Constant Time Approximation of Parameters of Bounded Degree Graphs”. In: Property Testing - Current Research and Surveys. Ed. by Oded Goldreich. Vol. 6390. Lecture Notes in Computer Science. Springer, 2010, pp. 234–239. doi: 10.1007/978-3-642-16367-8 14.

[BBB+24]

Alkida Balliu, Thomas Boudier, Sebastian Brandt, and Dennis Olivetti. “Tight Lower Bounds in the Supported LOCAL Model”. In: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024. Ed. by Ran Gelles, Dennis Olivetti, and Petr Kuznetsov. ACM, 2024, pp. 95–105. doi: 10.1145/3662158.3662798.

[BBC+25]

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, MarcOlivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. “Distributed Quantum Advantage for Local Problems”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025. Ed. by Michal Koucký and Nikhil Bansal. ACM, 2025, pp. 451–462. doi: 10.1145/3717823. 3718233.

[BBE+20]

Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. “Classification of Distributed Binary Labeling Problems”. In: 34th International Symposium on Distributed Computing, DISC 2020, Virtual Conference, October 12-16, 2020. Ed. by Hagit Attiya. Vol. 179. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 17:1–17:17. doi: 10.4230/LIPIcs.DISC.2020.17.

[BBG+26]

Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, and Jukka Suomela. “On the Universality of Round Elimination Fixed Points”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026. Ed. by Kasper Green Larsen and Barna Saha. SIAM, 2026, pp. 5066–5092. doi: 10.1137/1.9781611978971.183. 30

[BBH+21]

Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. “Lower Bounds for Maximal Matchings and Maximal Independent Sets”. In: Journal of the ACM 68.5 (2021), 39:1–39:30. doi: 10.1145/3461458.

[BBK+21]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees”. In: PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021. Ed. by Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen. ACM, 2021, pp. 283–293. doi: 10.1145/3465084.3467901.

[BBK+22]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed ∆coloring plays hide-and-seek”. In: STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022. Ed. by Stefano Leonardi and Anupam Gupta. ACM, 2022, pp. 464–477. doi: 10.1145/3519935.3520027.

[BBK+23]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed Maximal Matching and Maximal Independent Set on Hypergraphs”. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023. Ed. by Nikhil Bansal and Viswanath Nagarajan. SIAM, 2023, pp. 2632–2676. doi: 10.1137/1.9781611977554.ch100.

[BBK+26]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed ∆Coloring Plays Hide-and-Seek”. In: J. ACM 73.4 (2026), 28:1–28:58. doi: 10.1145/3819817.

[BBK+25]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Joonatan Saarhelo. “Towards Fully Automatic Distributed Lower Bounds”. In: 39th International Symposium on Distributed Computing, DISC 2025, Berlin, Germany, October 27-31, 2025. Ed. by Dariusz R. Kowalski. Vol. 356. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 13:1–13:19. doi: 10.4230/LIPIcs.DISC.2025.13.

[BBO22]

Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. “Distributed Lower Bounds for Ruling Sets”. In: SIAM Journal on Computing 51.1 (2022), pp. 70–115. doi: 10.1137/20m1381770.

[BCd+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 2026, Egham, United Kingdom, July 6-10, 2026. Ed. by Dennis Olivetti, Eric Ruppert, and Sean Ovens. ACM, 2026, pp. 301–310. doi: 10.1145/3796701.3815938.

[BGK+22] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. “Node and Edge Averaged Complexities of Local Graph Problems”. In: PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022. Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 4–14. doi: 10.1145/3519270.3538419. [BHO+19]

Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. “Hardness of Minimal Symmetry Breaking in Distributed Computing”. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. Ed. by Peter Robinson and Faith Ellen. ACM, 2019, pp. 369–378. doi: 10.1145/3293611.3331605.

[Bra19]

Sebastian Brandt. “An Automatic Speedup Theorem for Distributed Problems”. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. Ed. by Peter Robinson and Faith Ellen. ACM, 2019, pp. 379–388. doi: 10.1145/3293611.3331611. 31

[BFH+16]

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. “A lower bound for the distributed Lovász local lemma”. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. Ed. by Daniel Wichs and Yishay Mansour. ACM, 2016, pp. 479–488. doi: 10.1145/2897518.2897570.

[BO20]

Sebastian Brandt and Dennis Olivetti. “Truly Tight-in-∆ Bounds for Bipartite Maximal Matching and Variants”. In: PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020. Ed. by Yuval Emek and Christian Cachin. ACM, 2020, pp. 69–78. doi: 10.1145/3382734.3405745.

[CL21]

Corinna Coupette and Christoph Lenzen. “A Breezing Proof of the KMW Bound”. In: 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021. Ed. by Hung Viet Le and Valerie King. SIAM, 2021, pp. 184–195. doi: 10.1137/1.9781611976496.21.

[FRS+26]

Maxime Flin, Alesya Raevskaya, Ronja Stimpert, Jukka Suomela, and Qingxin Yang. “Brief Announcement: 2-Coloring Cycles in One Round”. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2026, Egham, United Kingdom, July 6-10, 2026. Ed. by Dennis Olivetti, Eric Ruppert, and Sean Ovens. ACM, 2026, pp. 44–47. doi: 10.1145/3796701.3815937.

[FL92]

Alan M. Frieze and Tomasz Luczak. “On the independence and chromatic numbers of random regular graphs”. In: Journal of Combinatorial Theory, Series B 54.1 (1992), pp. 123–132. issn: 0095-8956. doi: https://doi.org/10.1016/0095- 8956(92)90070- E. url: https://www.sciencedirect.com/science/article/pii/009589569290070E.

[GRB22]

Christoph Grunau, Václav Rozhon, and Sebastian Brandt. “The Landscape of Distributed Complexities on Trees and Beyond”. In: PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022. Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 37–47. doi: 10.1145/3519270.3538452.

[KS25]

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. IEEE, 2025, pp. 2292–2305. doi: 10.1109/FOCS63196.2025.00120.

[KS26]

Seri Khoury and Aaron Schild. “Breaking Barriers for Distributed MIS by Faster Degree Reduction”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC. ACM, 2026, pp. 1037–1048. doi: 10.1145/3798129.3800816.

[KMW16]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. “Local Computation: Lower and Upper Bounds”. In: Journal of the ACM 63.2 (2016), 17:1–17:44. doi: 10.1145/2742012.

[Lin92]

Nathan Linial. “Locality in Distributed Graph Algorithms”. In: SIAM Journal on Computing 21.1 (1992), pp. 193–201. doi: 10.1137/0221015.

[MRS+26]

Yannic Maus, Janosch Ruff, Sonia Simons, and George Skretas. “Distributed Symmetry Breaking on Hyperbolic Random Graphs”. In: CoRR abs/2607.09170 (2026). doi: 10.48550/ARXIV.2607.09170.

[MWW04]

Brendan D. McKay, Nicholas C. Wormald, and Beata Wysocka. “Short Cycles in Random Regular Graphs”. In: The Electronic Journal of Combinatorics 11.1 (2004), R66. doi: 10.37236/1819. 32

[PR01]

Alessandro Panconesi and Romeo Rizzi. “Some simple distributed algorithms for sparse networks”. In: Distributed Computing 14.2 (2001), pp. 97–100. doi: 10.1007/PL00008932.

Existence of high-girth graphs with the desired properties

In this section, we prove the following lemmas. Lemma A.1. There exist positive constants α, ∆0 , ε for which the following statement holds. For every sufficiently large n, and every ∆ satisfying that ∆0 ≤ ∆ ≤ n1/4 and that n∆ is even, there exists a ∆-regular graph G of n nodes that satisfies the following properties: 1. The girth of G is at least ε log∆ n. 2. The independence number of G is at most α(n/∆) ln ∆. Proof. Let γ > 0 be a sufficiently-small auxiliary constant, and define g = ⌊γ log∆ n⌋. We employ the probabilistic method on random regular simple graphs, and prove that with positive probability a graph has both claimed properties, for ε = γ/2 and α = 2C for a suitable constant C > 0. We sample uniformly at random a graph G′ of n nodes that is simple and ∆-regular. By [FL92, main theorem], there exist positive constants C, ∆0 , N such that, for every n ≥ N and every ∆0 ≤ ∆ ≤ n1/4 with n∆ even, it holds that, with probability 1 − o(1), the independence number of G′ is at most C(n/∆) ln ∆. By increasing ∆0 if necessary, assume that ∆0 ≥ 3. We have two cases. First, suppose that γ log∆ n < 4. Since the bound on the independence number holds with positive probability, there exists a realization G′′ of G′ that satisfies the bound. Since the graph is simple, G′′ has girth at least 3, while (γ/2) log∆ n < 2. Thus, G′′ already has girth at least (γ/2) log∆ n, and the claim follows. In the second case, γ log∆ n ≥ 4. In particular, g ≥ max{3, (γ/2) log∆ n}. We now count the numberP of small cycles in G′ . Let Xr denote the number of cycles of length exactly r, and define X<g = g−1 r=3 Xr . Observe that X<g counts the number of cycles of length strictly less than g. Let us define the quantity (∆ − 1)r Rr = max , log n . r By [MWW04, Lemma 1], applied with the set of cycle lengths {3, . . . , g − 1}, under the hypothesis (∆ − 1)2g−1 = o(n) stated in [MWW04, Eq. (1.1)], it holds with probability 1 − o(1) that Xr ≤ Rr for every 3 ≤ r < g. In our case, we have (∆ − 1)2g−1 ≤ ∆2g ≤ n2γ = o(n). Moreover, g−1 X (∆ − 1)r r=3

g−1 X ≤ (∆ − 1)r ≤ (∆ − 1)g ≤ nγ , r=3

where in the second inequality we used ∆ ≥ 3. Consequently, with probability 1−o(1), for sufficiently large n, it holds that ! g−1 g−1 X X (∆ − 1)r X<g ≤ Rr = O g log n + = O (g log n + ∆g ) = O (g log n + nγ ) ≤ n4γ . r r=3

r=3

Since the bound on the number of cycles and the bound on the independence number both hold with probability 1 − o(1), there is positive probability that G′ realizes both and, hence, a graph G′′ satisfying both bounds exists. We now want to remove these short cycles by keeping the graph ∆-regular. The final graph G. To construct the final graph G, we follow the degree-preserving edge-switching procedure used by Alon [Alo10, Lemma 2.1]. This procedure is iterative. The initial graph is F = G′′ . As long as F contains a cycle K of length strictly less than g, we pick an edge xy in K. We then choose another edge uv in F such that (a) The distance (in F ) between {u, v} and K is at least g. (b) The edge uv does not belong to any cycle of F of length strictly less than g. We define the new graph F ′ by deleting edges xy and uv, while we add edges xv and yu. This operation preserves ∆-regularity and simplicity. Indeed, property (a) implies that u, v ∈ / V (K) and that neither xv nor yu is already an edge of F . We now show that such an edge always exists and that this operation strictly decreases the number of cycles of length less than g. Then we set F = F ′ and we repeat the procedure until no short cycles exist. Existence of uv. We prove this fact inductively. The current graph contains at most n4γ cycles of length less than g (the base case is proved by construction of G′′ ). Since K has at most g − 1 nodes and the maximum degree is ∆, the number of nodes at distance less than g from K is at most g(1 + ∆ + . . . + ∆g−1 ) ≤ g∆g . By ∆-regularity, the number of edges incident to these nodes is at most g∆g+1 . Furthermore, the number of edges that belong to cycles of length less than g is at most gn4γ . Therefore, the number of edges that fail at least one of properties (a) and (b) is at most gn4γ + g∆g+1 . However, the graph has n∆/2 edges, and n∆ − gn4γ − g∆g+1 ≥ n1−5γ ∆ 2 for sufficiently small γ and sufficiently large n. In particular, at every iteration of the edge-switching procedure there exists an edge uv satisfying both properties (a) and (b). Switching edges strictly decreases the number of short cycles. Suppose F ′ contains a new cycle D of length less than g. Then, D must contain at least one of the new edges xv and yu. Suppose it contains xv but not yu. Removing xv from D gives an x-to-v path in F of length at most g − 2. Since x ∈ K, this contradicts property (a). The same argument holds if D contains yu but not xv. Suppose now that D contains both xv and yu. Removing these two edges splits D into two paths, all of whose edges belong to F . If these paths connect x to y and u to v, then property (b) implies that the u-to-v path has length at least g − 1, contradicting |D| < g. If, instead, the paths connect x to u and y to v, property (a) implies that both paths have length at least g, again contradicting |D| < g. Thus, the edge-switching creates no new short cycle and deletes K, decreasing the number of short cycles. The procedure terminates after at most n4γ iterations; let G be the resulting graph. By construction, G contains no cycle of length strictly less than g, and hence γ girth(G) ≥ g ≥ log∆ n. 2 Thus, G satisfies the first property of the lemma with ε = γ/2. 34

Small independence number. Let I be an arbitrary independent set of G. Every edge of G′′ with both endpoints in I must be one of the at most 2n4γ edges removed during the edge-switching procedure. By deleting from I one endpoint of every such edge, we obtain an independent set I ′ of G′′ satisfying |I ′ | ≥ |I| − 2n4γ . Therefore, |I| ≤ C

n ln ∆ n ln ∆ + 2n4γ ≤ 2C , ∆ ∆

where the last inequality holds by choosing γ sufficiently small and using ∆ ≤ n1/4 . Thus, the claim follows by setting α = 2C. Lemma A.2. There exist a sufficiently small constant c > 0 and a sufficiently large constant C > 0 such that, for all sufficiently large even n > 0, and for all 3 ≤ ∆ ≤ n1/4 , there exists a bipartite ∆-regular graph G = (V, E) on n nodes with the following properties: 1. The girth of G is at least c log∆ n. 2. Every maximal matching leaves at most C(n/∆) ln ∆ unmatched nodes. Proof. Let L and R be two disjoint sets of n/2 nodes each. Fix an auxiliary constant 0 < γ < 1/12, and let g = max {3, ⌊γ log∆ n⌋} . We first construct a random bipartite ∆-regular multigraph G′ on the node set L ∪ R such that, with positive probability, G′ satisfies the following two properties: 1. If A ⊆ L and B ⊆ R are such that |A| = |B| ≥ C(n/(2∆)) ln ∆, then there exists at least one edge connecting A to B. 2. The number of cycles of length strictly less than g is at most n2/3 . The multigraph G′ is constructed as follows: Attach ∆ half-edges to every node of L ∪ R. Let HL (HR ) be the set of half-edges attached to L (R). It holds that |HL | = |HR | = n∆/2. Then, pick a perfect matching between HL and HR uniformly at random. Each pair of matched half-edges produces an edge in the multigraph G′ , which is trivially ∆-regular. We now prove property 1. Let s = ⌈C(n/(2∆)) ln ∆⌉. If s > n/2, property 1 is vacuous, so assume that s ≤ n/2. Fix A ⊆ L and B ⊆ R such that |A| = |B| = s. Let HL [A] (HR [B]) be the subset of HL (HR ) of half-edges of A (B). Note that |HL [A]| = |HR [B]| = s∆. Now, order the elements of HL [A] arbitrarily, and reveal them one by one, together with their matched half-edges in HR . The random number of elements of HL [A] that are matched with an element of HR [B] is described by a hypergeometric distribution Hypergeometric(n∆/2, s∆, s∆). The probability that no element of HL [A] is matched with an element of HR [B] is therefore s∆−1 Y n∆ − s∆ − i s s∆ 2∆ 2 ≤ 1− n ≤ exp −2s , n∆ n 2 2 −i i=0 where holds by the known inequality 1 − x ≤ e−x for all 0 ≤ x ≤ 1. There are the latter inequality n/2 n/2 choices of A, and s choices of B. By the union bound, the probability that there exist s subsets A ⊆ L, B ⊆ R of size s such that no element of HL [A] is matched to an element of HR [B] is at most n 2 en 2s 2∆ 2∆ 2 exp −2s ≤ exp −2s n 2s n s 35

∆ en . = exp −s 2s − 2 ln n 2s By the definition of s, and since C is sufficiently large, the latter probability is at most h i exp [−s (C ln ∆ − 2 ln ∆ − 2)] ≤ exp −n3/4 , where we exploited the fact that C is sufficiently large, and that 3 ≤ ∆ ≤ n1/4 . Moreover, if one could find A ⊆ L, B ⊆ R of size strictly larger than s with no edge between A and B, then any two subsets A′⊆ A, B ′ ⊆ B of size exactly s are not adjacent. Therefore, with probability at least 3/4 1 − exp −n , property 1 holds. Now we prove property 2. Let X<g count the number of cycles of length strictly less than g. If P we define Xr to be the number of cycles of length exactly r, then X<g = g−1 r=2 Xr . Here, a cycle of length 2 consists of a pair of parallel edges. Since G′ is bipartite, Xr = 0 for all odd values of r. To bound E[Xr ], we consider rooted oriented representations of cycles of length r, for any r = 2k. A cycle can be represented as a sequence u1 v1 u2 v2 u3 . . . uk vk uk+1 , where uk+1 = u1 , ui ∈ L and vi ∈ R for all i. In such case, we say that the root is u1 , and the cycle is oriented from ui to vi and from vi to ui+1 . There are at most (n/2)2k possible such sequences, and, for each node in the sequence, we have at most ∆2 choices for the incoming and outgoing half-edge. Overall, among all possible choices of such sequences and of half-edges, we have (n/2)2k ∆4k candidates. Fix one − such candidate. For every i ∈ {1, . . . , k}, let a+ i , ai ∈ HL be the half-edges of ui used by the edges + ui vi and ui vi−1 , respectively, where indices are taken modulo k. Similarly, let b− i , bi ∈ HR be the half-edges of vi used by the edges ui vi and ui+1 vi , respectively. For a candidate representing a − + − cycle, the 2k half-edges a+ 1 , a1 , . . . , ak , ak must be pairwise distinct, and the same holds for the 2k + − + half-edges b− 1 , b1 , . . . , bk , bk . The candidate occurs precisely when the 2k = r prescribed pairs − {a+ i , bi }

+ {a− i+1 , bi },

and

i ∈ {1, . . . , k},

belong to the random perfect matching, where again the indices are taken modulo k. The probability that this happens is exactly 1 n∆ 2

n∆ 2 −1

n∆ 2 −2

...

n∆ 2 −r+1

Hence, E[Xr ] ≤ n∆ 2

n∆ 2 −1

n 2k 4k ∆ 2 n∆ 2 − 2 ...

n∆ 2 −r+1

Note that r < g = O(log n) and, hence, r ≤ n∆/4 for sufficiently large n. Hence, for all 0 ≤ j ≤ r −1, we have n∆/2 − j ≥ n∆/4, which we can replace in the inequality above, obtaining E[Xr ] ≤

n 2k 2

∆

4 n∆

= (2∆)2k . We distinguish two cases. If g = 3, then only cycles of length 2 contribute to X<g , and E[X<g ] = E[X2 ] ≤ (2∆)2 = 4∆2 ≤ 4n1/2 . 36

If g ≥ 4, then g = ⌊γ log∆ n⌋, and the estimates above imply E[X<g ] ≤ g(2∆)g . Moreover, (2∆)g ≤ ∆g log∆ (2∆) ≤ ∆2g ≤ n2γ , and hence E[X<g ] ≤ n3γ ≤ n1/2 for all sufficiently large n. Thus, in both cases, E[X<g ] = O(n1/2 ). By Markov’s inequality, Pr[X<g ≥ n2/3 ] = O(n−1/6 ) = o(1), proving property 2. Since both properties 1 and 2 hold with probability 1−o(1), a graph G′′ satisfying both properties must exist. In order to conclude the lemma, we must remove all short cycles by keeping the graph ∆-regular. The final graph G. We proceed by applying an iterative edge-switching procedure. Initially, let F = G′′ . As long as F contains a cycle of length strictly less than g, take any such cycle C and an edge xy in it, where x ∈ L and y ∈ R. We choose another edge uv of the current graph F , with u ∈ L and v ∈ R, such that (a) The distance in F between {u, v} and C is at least g. (b) The edge uv does not belong to any cycle of F of length strictly less than g. We obtain the next current graph F ′ by deleting xy and uv, and adding xv and yu. This operation preserves bipartiteness and ∆-regularity. We now show that such an edge uv always exists and that this operation strictly decreases the number of cycles of length less than g. Existence of uv. Inductively, the current graph F contains at most n2/3 cycles of length less than g: this holds initially by property 2, and the argument below shows that every switching strictly decreases their number. Since C has at most g − 1 nodes and the maximum degree is ∆, the number of nodes at distance less than g from C is at most g(1 + ∆ + . . . + ∆g−1 ) ≤ g∆g . The number of edges incident to these is at most g∆g+1 . Furthermore, the number of edges that belong to cycles of length less than g is at most gn2/3 . Therefore, the number of edges that fail at least one of properties (a) and (b) is at most gn2/3 + g∆g+1 . By the definition of g, ∆g ≤ max{∆3 , nγ } ≤ max{n3/4 , nγ }. Since g = O(log n), it follows that gn2/3 + g∆g+1 = o(n∆). As the graph has n∆/2 edges, for all sufficiently large n at least one edge remains after excluding all edges that fail (a) or (b). In particular, at every iteration there is at least one edge uv satisfying properties (a) and (b).

Switching edges strictly decreases the number of short cycles. Suppose that F ′ contains a new cycle D of length strictly less than g, that is, a cycle that was not already present in F . Then, D must contain at least one of the new edges xv and yu. Suppose it contains xv but not yu. Removing xv from D gives an x-to-v path in F of length at most g − 2. Since x ∈ C, this implies that the distance in F between v and C is less than g, contradicting property (a). The same argument holds for the case where D contains only yu and not xv. Suppose now that D contains both xv and yu. Removing these two edges splits D into two paths, all of whose edges belong to F . If these paths connect x to y and u to v, then property (b) implies that the u-to-v path has length at least g − 1: otherwise, this path together with uv would be a cycle of F of length less than g. This gives |D| ≥ g + 1, a contradiction. In the other case, the paths connect x to u and y to v. Since x, y ∈ C, property (a) implies that both paths have length at least g, again contradicting |D| < g. Thus, the switching creates no new cycle of length less than g. It deletes at least the selected cycle C, because xy is removed, so the number of short cycles strictly decreases. The procedure therefore terminates after at most n2/3 iterations; let G be its final graph. If γ log∆ n < 4, then γ g ≥ 3 > log∆ n. 2 Otherwise, γ g ≥ ⌊γ log∆ n⌋ ≥ log∆ n. 2 Thus, G has the girth required in the statement after setting c = γ/2. Moreover, the construction produces no loops, and the switching procedure removes every cycle of length 2. Therefore, the final graph G is simple. Every maximal matching in G is large. Let t ≤ n2/3 be the number of switchings that we perform to obtain G from G′′ . Since every switching removes two edges, there are at most 2t edges that are present in G′′ that do not belong to G. Let M be an arbitrary maximal matching in G, and let UL ⊆ L and UR ⊆ R be the sets of unmatched nodes. We trivially have |UL | = |UR |, and there is no edge between these two sets (otherwise we could increase the size of the maximal matching). This implies that if, in G′′ , there were edges between UL and UR , these must have been removed during edge-switching. For all such removed edges, we consider the subset UL′ where we remove the endpoints of these edges from UL . We have |UL′ | ≥ |UL | − 2t. Trivially, there is no edge between UL′ and UR in G′′ . Consider a subset UR′ ⊆ UR such that |UL′ | = |UR′ |. Then, by property 1 in G′′ , we have that |UL′ | = |UR′ | < C(n/(2∆)) ln ∆. Hence, |UL | − 2t ≤ C

n ln ∆ , 2∆

which implies that n ln ∆ + 2t. 2∆ Therefore, the total number of unmatched nodes is at most |UL | ≤ C

n ln ∆ + 4t 2∆ n ln ∆ ≤ 4C , 2∆

|UL | + |UR | ≤ 2C

where the latter holds because t ≤ n2/3 = o(n ln ∆/∆) uniformly over 3 ≤ ∆ ≤ n1/4 . After increasing the constant C by a factor of two, this is the bound claimed in the statement.

Record · ID 1108707 · SHA-256 ed05c8614e939bd3
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.