Conceptio › Archive › arXiv CS

arXiv CSopen access

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

arXiv:2605.19078v1 [cs.DS] 18 May 2026

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes Arnold Filtser

Orr Fischer

Bar-Ilan University [email protected]

Abstract In the t-Proof Labeling Scheme model (t-PLS model), our goal is to certify that a network of nodes satisfies a given property P . A prover assigns a label to each node, and each node decides to accept or reject based on its labeled t-hop neighborhood. If P holds, there exists a labeling that makes all nodes accept. If P does not hold, in all labelings at least one node rejects. The cost of a scheme is its maximum label size. The Tradeoff Conjecture [Feuilloley, Fraigniaud, Hirvonen, Paz, and Perry, DISC 18, Dist. Comput. 21] hypothesizes that the existence of a 1-PLS for a property P with cost p implies the existence of a t-PLS for P with cost O(⌈p/t⌉). The conjecture was initially shown to hold √ e for specific graph classes, such as trees, cycles, and grids. Later, a weaker O(⌈∆p/ t⌉) cost was shown for fixed minor-free graphs, where ∆ is the maximum degree. In this work we resolve the Tradeoff Conjecture, up to a single logarithmic factor. In general graphs, we show that the existence of a 1-PLS with cost p implies the existence of an O(t log n)PLS with cost O(⌈p/t⌉) for the same property. For fixed minor-free graphs (which include e.g. planar graphs), we show that the existence of a 1-PLS with cost p implies the existence of a t-PLS with cost O(⌈p/t⌉ + log n) for the same property. We also refute a previously suggested stronger variant of the Tradeoff Conjecture, and show that having very large t-hop neighborhoods is an insufficient condition for obtaining a tradeoff better than O(⌈p/t⌉).

Contents 1 Introduction 1.1 Technical Overview . . . . . . . . . . .

5 Tradeoff Theorem for General Graphs 5.1 Helpful Sequential Algorithm for Find1 ing a (O(t log n), 1/t)-TS Partition . . 2 5.2 Labeling Scheme for General Graphs .

2 Preliminaries

3 Two-Separated Partitions and ClusterDegeneracy 10 4 Tradeoff Graphs

Theorem

for

6 Refuting Stronger Variants Tradeoff Conjecture

18 18 21

the 25

A Missing Proofs from Section 4

16 B Missing Proofs from Section 5

Minor-Free

Introduction

In distributed proof labeling schemes (the PLS model), our goal is to verify that a network of nodes satisfies a given property P . The PLS model was first introduced by [KKP10], and has been studied in the context of distributed verification, with the aim of locally certifying that a network is in a valid state while storing compact labels on the nodes. Beyond verification, the PLS model has direct applications in the design of self-stabilizing protocols and in the study of local algorithms (See [Feu21] for a survey). Formally, for a graph G = (V, E) with some auxiliary inputs I (e.g. edge weights), a proof labeling scheme certifying a property P of (G, I) consists of a pair Π = (Prov, Ver), where Prov is a prover strategy that assigns a label to each node, and Ver is a verification algorithm executed by every node following a label assignment. Each node v decides to accept or reject based on its label and the label of its neighbors. The scheme must satisfy two conditions: • Completeness: if (G, I) satisfies P , all nodes accept given the labeling of the prover Prov. • Soundness: if (G, I) does not satisfy P , then for every labeling at least one node rejects. The cost of a scheme Π is the maximum label size assigned by the prover Prov, as a function of the graph size |V (G)| = n. In the generalized t-PLS model, nodes may decide to accept or reject based on their t-hop neighborhood and the labels of the nodes in this neighborhood, instead of just their immediate neighborhood. This extension is motivated by the study of space-time tradeoffs, as it allows the verifier to use t rounds of communication (instead of one) to potentially reduce the label sizes. In this model, many tradeoffs have been studied for specific problems, such as acyclicity [OPR17], MST and shortest path problems [FFH+ 21], colorings [ACF+ 23, FJKS24], and dominating sets [FJKS24]. On the other hand, some works investigated space-time tradeoffs of any property P [OPR17, FFH+ 21, FOS21, BFZ25]. The focus of our work is on this latter category. The t-PLS model was first defined by Ostrovsky, Perry, and Rosenbaum [OPR17], who showed that any property P can be certified by a t-PLS with cost O(min(n2 , m log n)/t). Following this work, Feuilloley, Fraigniaud, Hirvonen, Paz, and Perry [FFH+ 21] showed that for trees, cycles, and grids, any 1-PLS for a predicate P with cost p can be transformed into a t-PLS for P with cost O(⌈p/t⌉). They raised the question of whether this tradeoff can be obtained in general, in a conjecture later known as the Tradeoff Conjecture. The conjecture was raised again as an open question in [FOS21, ACF+ 23, FJKS24, BFZ25] and the survey [Feu21]. Conjecture 1.1 (The Tradeoff Conjecture [FFH+ 21]). If there exists a 1-PLS for a predicate P on all graphs with cost p = p(n), then for any t ≥ 1, there exists a t-PLS for P with cost O(⌈p/t⌉). We resolve the weak version of the conjecture (mentioned as Problem 1 in [FFH+ 21]). Specifically, we prove that the Tradeoff Conjecture holds, up to a single multiplicative log n factor. To our knowledge, this is the first tradeoff for any P and for all graphs depending on the cost of the 1-PLS. In the following, a configuration family (G, I) is a pair consisting of a graph family G and a set of possible auxiliary inputs I. Theorem 1.2. Let (G, I) be a configuration family, and P a predicate on (G, I). For G ∈ G with |V (G)| = n, if there exists a 1-PLS for P with cost p, then for any t ≥ 1 there exists an O(t log n)-PLS for P with cost O(⌈p/t⌉).

Consider the problem of MST verification in graphs with integer polynomial edge weights. Kutten and Peleg [KK07] constructed a 1-PLS with cost O(log2 n). Later, Feuilloley et al. [FFH+ 21] constructed a t-PLS with cost O(⌈log2 n/t⌉). However, their t-PLS can only be applied for t = O(log n). Thus, the scheme of [FFH+ 21] has cost Ω(log n) even for very large t. By applying our black-box Theorem 1.2 combined with [KK07], we get a general tradeoff, and an improvement over [FFH+ 21] for the parameter range t ≥ log2 n. In particular, for t = Ω(log3 n), we get constant cost. Corollary 1.3 (t-PLS for MST verification). For any t ≥ log n, there exists a t-PLS for the MST verification problem with cost O(⌈log3 n/t⌉). Next, we prove that the Tradeoff Conjecture holds in fixed minor-free graphs, up to a single addi√ e tive log n factor. Previously, Fischer, Oshman and Shamir [FOS21] showed a bound of O(⌈∆p/ t⌉) on the cost, where ∆ is the maximum degree in the graph. Our result removes the dependence in ∆, and improves the dependence on t quadratically. Many well-known graph families are minor free, such as planar graphs, as well as graphs of bounded genus or treewidth. We state our results for Kr -minor free graphs, which are in particular H-minor free for any H such that |V (H)| ≤ r. Theorem 1.4. Let r ≥ 1 be a constant, and let (G, I) be a configuration family where G is the family of all Kr -minor free graphs, and let P be a predicate on (G, I). If there exists a 1-PLS for P in (G, I) with cost p, then for any t ≥ 1, there exists a t-PLS for P in (G, I) with cost O(⌈p/t⌉ + log n). In [FFH+ 21], the authors additionally asked whether the tradeoff might scale linearly with the ball growth of the graph b(t) = minv |Bt (v)|,1 although they considered this to be most likely false. Question 1.5 ([FFH+ 21] Open Problem 2). Assuming there exists a 1-PLS for a predicate P on e graphs with cost p = p(n), does there exist for any t ≥ 1 a t-PLS for P with cost O(⌈p/b(t)⌉)? We confirm that this does not hold, and show that even if all t-neighborhoods are of size Ω(n), the best scaling possible is Ω(⌈p/t⌉). Moreover, this phenomenon already occurs in planar graphs. Theorem 1.6. There exists a predicate P on an infinite family of planar graphs G = {Gt,m }∞ t,m=1 and on some auxiliary input set I, where for Gt,m ∈ G we have minv∈V (Gt,m ) |Bt (v)| = Ω(|V (Gt,m )|), and there is a 1-PLS for P with cost O(m), but any t-PLS for P has cost Ω(m/t). Additional related works: The PLS model (i.e. 1-PLS model) has been extensively studied in a broad range of topics, such as for various graph properties [KK07, KKP10, GS16, CHPP20], for properties expressible in some logic frameworks [FBP22, FMRT24, CKM25], and for memberships in graph classes [FFM+ 21, BFP24]. Given the very rich literature on PLS, we refer to the survey on local certification and the PLS model of Feuilloley [Feu21], as well as the surveys on related topics of Feuilloley and Fraigniaud [FF16], and of Suomela [Suo13].

1.1

Technical Overview

We begin by presenting a key framework for obtaining tradeoff theorems, used both in prior works and in our work, which shows how the existence of certain graph decompositions directly yields 1

Bt (v) = {u ∈ V | distG (v, u) ≤ t} denotes the ball around v of radius t w.r.t. the shortest path metric of G.

tradeoff theorems. We then introduce a new type of decomposition, called Two-Separated partitions (TS partitions), which extends the prior decompositions while implying similar tradeoff theorems. Following this, we show three constructions of TS partitions in graphs: (a) a warmup construction which yields a weaker tradeoff theorem for general graphs (cf. Theorem 1.2), but its ideas are used throughout the paper, (b) constructing TS partitions from padded decompositions (introduced later), which implies our results for minor free graphs (Theorem 1.4), and (c) a construction which yields our tradeoff theorem for general graphs (Theorem 1.2). Finally, we discuss the techniques for refuting the stronger variant of the Tradeoff Conjecture (Theorem 1.6). Tradeoff from partition-based decompositions: To obtain Theorems 1.2 and 1.4, we use a variation on a partition-based framework previously used in [FFH+ 21, FOS21]. Before introducing our variation, we first informally describe this framework as it appears in prior works. The key combinatorial object needed for this framework is the existence of a decomposition of the graph into connected clusters C1 , . . . , Ck , each of diameter at most α · t (for some small enough constant α ≤ 1), such that for the set of boundary vertices2 Xi of Ci we have that ∀i |Xi |/|Ci | ≤ ε for some small ε = ε(n, t). Given such a decomposition, we describe how to construct a t-PLS Πt from a 1-PLS Π1 , while paying only roughly an ε-fraction of the cost of Π1 . Specifically, if Π1 costs p, we need to construct a labeling for every graph G satisfying P , such that the maximum label size is roughly O(⌈εp⌉), and describe a verifier function that accepts this labeling, but rejects all labelings on graphs not satisfying P . Label construction for Πt : Recall that G satisfies P if and only if there is some labeling ℓV for Π1 , such that all nodes accept according to Π1 . We describe a t-PLS Πt that certifies P by proving to the nodes that such a labeling ℓV exists. Assume that a 1-PLS ℓV exists with cost p. We create the t-PLS labels of the vertices in cluster Ci by taking the 1-PLS labels of its boundary vertices {ℓV (x)}x∈Xi , and splitting them among all the cluster vertices (say lexicographically). Additionally, each vertex v ∈ Ci will get an auxiliary label containing additional information so that v can identify its cluster Ci . We denote the maximum possible size of the l auxiliary m label by c, and call it description cost. |Xi | The resulting label size of Ci vertices will be O |Ci | · p + c = O (⌈εp⌉ + c). Thus the cost of Πt is O (⌈εp⌉ + c). Verification under Πt : For each cluster Ci , a leader vi ∈ Ci is designated. Given the labels of Ci , vi can reconstruct the labels ℓV (x) for all boundary vertices x ∈ Xi . Further, let C̄i be the collection of clusters with edges also incident to Ci (i.e. neighboring clusters, excluding Ci ), and by X̄i = ∪Cj ∈C̄i Xj the union of their boundary vertices. Note that for each cluster Cj ∈ C̄i , as all Cj vertices are at distance ≤ 2α · t from vi , vi can reconstruct the cluster Cj , and the Π1 -labels of its boundary vertices Xj . In other words, vi can compute {ℓV (x)}x∈X̄i . We observe the following: • For every v ∈ Ci \ Xi , all its neighbors are in Ci . • For every x ∈ Xi , all its neighbors are in Ci ∪ X̄i . All Ci vertices other than the leader vi will accept regardless of the input. vi will accept iff there are labels {ℓV (v)}v∈Ci \Xi for the non-boundary vertices so that all Ci vertices (including Xi ) will be accepted by the Π1 -verifier simultaneously (with accordance to the given labels of X̄i ∪ Xi ). 2 The boundary Xi of a cluster Ci consists of all the vertices in Ci with neighbors out of Ci . Formally, Xi = Ci ∩ B1 (V \ Ci ), where B1 (S) is the ball of radius 1 around S.

Showing completeness and soundness is now straightforward. If (G, I) satisfies P , and a Π1 labels indeed exists, each leader vi can use them to convince itself that there are satisfying labels and thus will accept. For soundness, one can use the fact that there are no edges between yet undetermined (i.e. non-boundary) vertices in different clusters, and thus if each leader vi accepts separately, the combined labels they computed will satisfy the Π1 -verifier, and thus by the soundness of Π1 , (G, I) satisfies P . Challenge: As it turns out, constructing decompositions such that the fraction of boundary vertices is small in all the clusters simultaneously is quite challenging. In the following, we describe how we can relax the requirements from the decomposition to get considerably better results. New combinatorial notions - Two-Separated partitions and cluster-degeneracy: In the previous part, we discussed how the existence of a decomposition into connected clusters C1 , . . . , Ck , with diameter O(t) and boundary-to-size ratio of |Xi |/|Ci | ≤ ε directly implies a tradeoff theorem in which the t-PLS costs an ε-fraction of the original 1-PLS. As our first contribution, we present the notion of a Two-Separated partition (TS partition), which generalizes the decomposition above while still implying the same tradeoff guarantees. A (t, ε)-Two-Separated partition is a pair (C, X) where X ⊆ V is called the separating set, and C is a partition of V , satisfying (a) for i ̸= j, any path between two nodes u ∈ Ci \ X and v ∈ Cj \ X must contain two consecutive vertices in X, (b) every cluster in C has weak diameter at most t,3 and (c) maxi |Ci ∩ X|/|Ci | ≤ ε. (See Figure 1(a) for an example) Conceptually, this new decomposition allows the set Xi = Ci ∩ X to differ from the boundary of the cluster Ci . This allows, for example, for a cluster to be disconnected, as long as it has a low weak-diameter, and also allows a more flexible manner to balance how much “boundary information” is encoded on each cluster. Using essentially the same technique as the partitionbased schemes, we show that the existence of a (t, ε)-TS partition implies that a 1-PLS with cost p can be turned into an “equivalent” O(t)-PLS with cost O(⌈εp⌉ + c) for some description cost c. Our main method in the paper of constructing (t, ε)-TS partitions is through the notion of ε-cluster-degeneracy, introduced next. A partition of V into an ordered set of clusters C = {C1 , . . . , Ck } has ε-cluster-degeneracy if ∀i ∈ [k], v ∈ Ci | distG v, V \ ∪ij=1 Cj ≤ 2 ≤ ε · |Ci |. See Figure 1(b) for a pictorial example. We show that a decomposition into clusters with ε-clusterdegeneracy and weak diameter at most t implies the existence of a (t, ε)-TS partition (Lemma 3.1). As stated above, the existence of these decompositions directly implies a tradeoff theorem, where the cost is O(⌈εp⌉) + the description cost of the TS partition. Thus our primary effort is aimed at showing the existence of TS partitions with small description cost. In the following parts we present three constructions of TS partitions, for both general and minor free graphs. Warmup - a simple solution for general graphs: As a warmup, we consider a simple ball carving process that outputs for any graph a decomposition into clusters with (1/t)-clusterdegeneracy and weak diameter O(t log n). That is, we show that V can be partitioned into clusters 3

The weak diameter of a cluster C is maxu,v∈C distG (u, v) the maximum pairwise distance w.r.t. the original distances. In particular, a cluster may be disconnected.

C5 C4 C6

C1 C8

C7 C10

C9 C10

Figure 1: (a) Illustration of a (5, 2/3)-TS partition. Nodes of X marked in red. All clusters have weak diameter ≤ 5, where some clusters are internally disconnected. Worst red nodes to size ratio is in the bottom-right cluster, with ε = 2/3. All white-to-white paths between clusters must pass two consecutive red nodes. (b) Illustration of cluster-degeneracy. In the example, we highlight for C7 its 2-boundary with the clusters that follow it. We remark that in general, clusters can be disconnected. C1 , . . . , Ck , each of weak diameter O(t log n), such that ∀i ∈ [k], v ∈ Ci | distG v, V \ ∪ij=1 Cj ≤ 2

≤ |Ci |/t.

The process works in iterations. For iteration i ≥ 1, assume we are given some set of alive nodes Li ̸= ∅, initialized as L1 = V . We take an arbitrary node vi ∈ Li , and consider balls of growing radius centered at vi . We say that a ball Bj (vi ) of radius j ≥ 2 is expanding if |Bj (vi ) ∩ Li |/|Bj−2 (vi ) ∩ Li | > 1 + 1/t. We note that there exists a non-expanding ball centered at vi of radius O(t log n). Otherwise, due to the many expanding layers, we have |BO(t log n) (vi )| ≥ (1 + 1/t)Θ(t log n) > n.4 If we find a non-expanding ball Bj (vi ), we define the cluster Ci = Bj (vi ) and set Li+1 = Li \ Ci , terminating when Li+1 = ∅. Using simple calculations, it is easy to see that the resulting clusters are (1/t)-cluster-degenerate: Each cluster is a non-expanding ball, whose cluster’s size is |Br (vi ) ∩ Li |, and its 2-hop boundary with subsequent clusters is |(Br (vi ) \ Br−2 (vi )) ∩ Li |. Therefore by definition of a non-expanding radius, we have |(Br (vi ) \ Br−2 (vi )) ∩ Li | = |Br (vi ) ∩ Li | − |Br−2 (vi ) ∩ Li | ≤ (1/t) · |Br (vi ) ∩ Li | = |Ci |/t . We conclude that a (O(t log n), 1/t)-TS partition exists in any graph. Furthermore, using standard arguments, one can show that any TS partition can be described with a cost of O(log n) bits (See Lemma 4.5). This immediately implies that any 1-PLS for a property P with cost p can be transformed to an O(t log n)-PLS for P with cost O(⌈p/t⌉ + log n). However, many properties of interest (e.g. computing a spanning tree [KKP10, GS16], MST [KK07], or certifying planarity [FFM+ 21]) have a 1-PLS with logarithmic or close to logarithmic cost. Ideally we would like a t-PLS for any property, that converges to constant cost as t grows. We could obtain this if we could reduce the additive factor in the tradeoff to be bounded by a constant. Therefore, a natural question to ask is whether there exists a TS partition with the parameters 4

We remark that if Bj (vi ) contains all alive nodes, then Bj+2 (vi ) is a non-expanding ball.

above, but with constant description cost? Another natural question is whether we can remove the multiplicative dependency of the tradeoff in n, at least for some large graph class? We positively answer the two questions, as discussed next. Kr -Minor free graphs and padded decompositions: In Section 4, we show that for the class of Kr -minor free graphs (for constant r ≥ 1), any 1-PLS for a property P with cost p can be transformed into a t-PLS for P with cost O(⌈p/t⌉ + log n), which is optimal up to a single additive logarithmic factor.5 The main tool we use is the existence of good “padded decompositions” in these graphs. See Definition 6 for a formal definition of padded decomposition. Here it will suffice to note that if a graph has padding parameter β > 0, then for any t = Ω(1), there is a randomized partition of V into clusters, such that (a) each cluster has weak diameter at most t, and (b) for every node v ∈ V , Pr(B2 (v) ⊈ Cv ) ≤ 2β/t, where Cv is the unique cluster containing v, and B2 (v) is the ball of radius 2 centered at v.6 The padding parameter β of different graphs is a widely studied topic that has many algorithmic applications (See [CF25] and the references therein). It is known that for Kr -minor free graphs β = Θ(log r) [CF25] (O(1) if r is constant), while in general graphs β = Θ(log n) [Bar96]. As we next show, the existence of padded decompositions with low padding parameter β in a graph G implies the existence of a good TS partition in G. We start by showing that graphs with padding parameter β have some cluster C ⊆ V with weak diameter at most t, and |C ∩B2 (V \C)| ≤ (2β/t)|C|. Let us sample a random padded decomposition with padding parameter β and weak diameter t, i.e. a randomized partition into clusters {C1 , . . . , Ck }, such that the weak diameter of the clusters is at most t, and that property (b) holds. Let Γ2 be the 2-boundary of the clusters, i.e. Γ2 = {v | distG (v, V \ Cv ) ≤ 2}. We notice that property (b) of the decomposition is equivalent to: Pr(v ∈ Γ2 ) = Pr(B2 (v) ⊈ Cv ) ≤ 2β/t. Therefore, by linearity of expectation, E(|Γ2 |) ≤ (2β/t) · n. We notice that ! ! k k X X min |Ci ∩ Γ2 |/|Ci | ≤ |Ci ∩ Γ2 | / |Ci | = |Γ2 |/n, i∈[k]

i=1

where the first inequality follows from the mediant inequality.7 In expectation, we have E(min |Ci ∩ Γ2 |/|Ci |) ≤ E(|Γ2 |)/n ≤ 2β/t. i∈[k]

We conclude that by the probabilistic method, there exists a cluster C such that |C ∩ B2 (V \ C)| ≤ (2β/t)|C|. Moreover, using the same argument one can show that for any set L ̸= ∅, we can find a cluster C ⊆ L with weak diameter at most t and |C ∩ B2 (L \ C)| ≤ (2β/t)|C ∩ L|. Given the existence of such a cluster C, we can perform a similar ball carving process as in the warmup. We define a process with iterations where in iteration i ≥ 1 we are given some set of 5 See e.g. Theorem 1.6 for an Ω(1/t) lower bound on the tradeoff of some problems, though there are many such bounds in the literature. 6 Recall that the partition is randomized, meaning the randomness is taken over its distribution. 7

Pℓ

i The mediant inequality states that if a1 , b1 , . . . , aℓ , bℓ > 0 are real numbers, then mini∈[ℓ] abii ≤ Pi=1 . ℓ b i=1

alive nodes Li ̸= ∅, initialized as L1 = V . Using the padded decomposition, we argue that there exists some cluster Ci such that |Ci ∩ B2 (L \ Ci )| ≤ (2β/t)|Ci |. We add Ci to our partition, and set Li+1 = Li \ Ci , terminating if Li+1 = ∅. The resulting partition can be shown to be a partition into clusters with weak diameter t, and (2β/t)-cluster-degeneracy, which for Kr -minor free graphs translates to O(1/t)-cluster-degeneracy, and implies Theorem 1.4. Interestingly, by using the optimal padded decomposition of general graphs [Bar96], we also obtain an alternative method to the same result as in the warmup - that a 1-PLS for a property P with cost p can be transformed to an O(t log n)-PLS for P with cost O(⌈p/t⌉ + log n). General Graphs, with Constant Description Cost: In Section 5, we show that for the class of all graphs, any 1-PLS for a property P with cost p can be transformed into an O(t log n)-PLS with cost O(⌈p/t⌉). This cost’s additive factor is bounded by a constant, hence this scheme converges to a constant number of bits as t grows. Our goal is to adapt the construction of the warmup to obtain an (O(t log n), 1/t)-TS partition that can be locally described using O(1) bits per node. Attempt 1 - Ball carving with advice: We design a compact description for the warmup construction. Recall that in this process we took in each step some living node v, carved a ball Br (v) around it for some r, added it to our clusters, and removed Br (v) from the set of living nodes. Let us further assume that we iterate over the vertices in increasing order of id, i.e. in each step we take the node with the smallest identifier that is still alive. We describe a label of size O(log t + log log n) which allows nodes to recognize their cluster, given their labeled O(t log n)-neighborhood: we mark for each node v if a ball Br(v) (v) was taken as a cluster, and if so, its radius r(v). We note that a node u can locally simulate the process, and deduce its cluster, by finding the node v with the smallest id in its O(t log n) neighborhood such that u ∈ Br(v) (v), and assigning itself to a cluster with identifier ID(v). Similarly, node u can repeat this process for each node in its surrounding, deducing the entire cluster. Given an additional label for marking nodes in the separating set X, a node can verify that all the TS partition properties hold. The only real cost of this scheme is describing the radius for each node. One natural approach to reduce the cost is to encode this information across each cluster, however there is no guarantee the clusters are sufficiently large to ensure it can be stored by constant size labels. We instead take a different approach: We observe that sharing some common string S across the graph is much cheaper than assigning each node v some distinct string Sv of its own (See [OPR17, FFH+ 21, FOS21]). Therefore, instead of describing the radii explicitly, we would like some shared string from which all nodes could deduce their encoded radius, as well as the radii of nodes in their O(t log n)neighborhood. As our key observation we show that picking a random radius for each node is good, assuming additional alterations to the process. Therefore, assuming all nodes have access to a long shared randomness string, they can deduce the radius of every node. We then condense this string to O(log n) bits using randomness reduction techniques, and have the prover share a good random string for our graph G across all nodes. We describe the new process, and explain how to identify clusters. Solution - Ball carving with randomized radius: Assume we have a given random string R. The new process runs in iterations i = 1, . . . , n, where we iterate over the vertices in lexicographic order while maintaining the set of currently living (unclustered) nodes Li , where we iterate over vi even

if vi ∈ / Li . In step i, we check whether vi has a living node within distance 2t log n. If it does, it samples a random even radius ri ∈ [2t log n + 2, 8t log n] using R, and considers the candidate cluster Ci = Bri (vi ) ∩ Li (which does not contain vi if vi ∈ / Li ). As before, we take the cluster Ci = Bri (vi ) ∩ Li if it does not expand, i.e. if |Bri (vi ) ∩ Li |/|Bri −2 (vi ) ∩ Li | ≤ 1 + 1/t. then Ci is carved out of Li and its 2-boundary with subsequent clusters is added to X. The output is the carved clusters C together with the marked boundary nodes X, which we show (with high probability) form an (O(t log n), 1/t)-TS partition. Intuitively, we show that in any fixed step i, the cluster Ci is non-expanding with constant probability over the choice of ri . Moreover, because we iterate over all nodes (even those already clustered), and since every node u is contained in B2t log n (vi ) for Ω(t log n) different nodes vi , we get that all nodes are clustered with high probability. Unlike the prior attempt, all a node u needs to know to identify its cluster is (a) the randomness string, (b) for every node v in its vicinity, whether its cluster was taken, and (c) whether v is in X. All this information can be shared with v using O(1) bits, using some randomness reduction technique, and a dedicated PLS. Refutation of the stronger variant of the Tradeoff Conjecture: In Section 6, we show that having Θ(n)-sized t-neighborhoods is insufficient for obtaining a tradeoff better than O(⌈p/t⌉), even for the case of planar graphs, refuting the stronger variant of the Tradeoff Conjecture as discussed above. We do so by defining our predicate P as an equality problem between distant nodes, and reduce it to 2-player non-deterministic equality. Our construction is very simple. We design a layered graph with 2t + 3 layers, where odd layers have one node, and even layers have m nodes, with the nodes of each layer connected to all nodes of the neighboring layers (See Figure 2). The leftmost and rightmost nodes, v 1 and 2 v 2t+3 , receive inputs I(v 1 ) and I(v 2t+3 ) from {0, 1}m , and we define the predicate P to assert that I(v 1 ) = I(v 2t+3 ). We design a 1-PLS where even layers relay and split I(v 1 ) into m parts, each part given to some node in the layer, which requires a label size O(m) bits per node. We show that a t-PLS on P with cost p implies a 2-player non-deterministic equality protocol of cost O(p · m · t). In combination with the fact that m2 -bit equality costs Ω(m2 ) in the 2-player model, we obtain a lower bound of Ω(m/t) on the cost of any t-PLS for P . We remark that one can easily transform P into a pure graph property (i.e. without any auxiliary input) by encoding I(v 1 ), I(v 2t+3 ) through two low-diameter subgraphs with Θ(m2 ) edges connected to v 1 , v 2t+3 respectively. However the graph then is not necessarily planar. For planar graphs, a similar graph property with 1-PLS of cost O(log m), versus t-PLS of cost Ω(log m/t) can be easily shown by encoding two low-diameter graphs with Θ(m) edges next to each of the nodes v 1 , v 2t+3 .

Preliminaries

We denote [k] = {1, . . . , k}, and [k1 , k2 ] = {k1 , . . . , k2 }. Given functions f1 , f2 with disjoint domains, the combined function is defined as f = f1 ∪ f2 , where f (x) = f1 (x) if x ∈ Dom(f1 ), and f (x) = f2 (x) if x ∈ Dom(f2 ).

v12

v14

v16

v1 v

2 vm

4 vm

v12t+2

v18

6 vm

8 vm

v 2t+3

v 2t+1

2t+2 vm

Figure 2: The graph Gt,m . It has 2t + 3 layers, and in each even layer has m nodes. The leftmost and rightmost nodes of the graph v 1 , v 2t+3 receive as input some strings I(v 1 ), I(v 2t+3 ), and the configuration is in P if I(v 1 ) = I(v 2t+3 ). Graph notation: For a graph G = (V, E), and a pair of vertices u, v ∈ V , distG (u, v) denotes the shortest path metric in G (that is the minimum number of edges in a u-v path). For V1 , V2 ⊆ V , let E(V1 , V2 ) = {{vi , vj } ∈ E | vi ∈ V1 , vj ∈ V2 } be the edges between V1 , V2 . G[C] = (C, E(C, C)) denotes the induced graph on C, i.e. it contains the edge set {{u, v} ∈ E | u, v ∈ C}. The (strong) diameter of a cluster C ⊆ V is the maximum pairwise distance in the induced graph: maxu,v∈C distG[C] (u, v), while the weak diameter is the maximum pairwise distance w.r.t. original distance: weak-diam(C) = maxu,v∈C distG (u, v). We note that C can have a finite weak diameter while not being connected. A partition C of V is weakly/strongly Λ-bounded if every cluster has weak/strong diameter at most Λ. Let N (v) ⊆ V denote the neighborhood of v. For an integer t ≥ 1, let Bt (v) = {u ∈ V | distG (u, v) ≤ t} ⊆ V be the t-hopSneighborhood of v in G, also called the ball of radius t around v. For a set V ′ ⊆ V , let Bt (V ′ ) = v∈V ′ Bt (v). A graph H is said to be a minor of G if H can be obtained from G by a series of vertex deletions, edge deletions, and edge contractions.8 The family of H-minor free graphs consists of all graphs G that do not contain H as a minor (i.e., no series of operations leads from G to H). String notation: Given a collection of strings S1 , . . . , Sℓ , let (S1 , . . . , Sℓ ) denote a single string obtained by concatenating S1 , . . . , Sℓ using a fixed delimiter scheme, so that from (S1 , . . . , Sℓ ) one can uniquely recover the number of strings ℓ and each of the strings S1 , . . . , Sℓ . With some abuse of notation, we use (S1 , . . . , Sℓ ) to denote both the tuple of strings and its encoded representation as a single string; the intended meaning will always be clear from context. For an integer p, let {0, 1}≤p denote the set of all binary strings of length at most p. For an integer m, let Pad(S, m) denote an encoding of S as a string whose length is the smallest multiple of m that is larger than |S|, such that S can be uniquely recovered from Pad(S, m). We remark that both the delimiter scheme and the padding scheme can be trivially implemented by implementing a larger alphabet over the binary encoding. Proof Labeling Schemes: For a graph family G and set of strings I, a (G, I)-configuration is a pair (G, I) where G ∈ G is a graph, and I : V → I is an assignment of inputs to the nodes of G. A typical example of additional inputs I that can be given to nodes is weights on incident edges, such as in the MST problem [KK07], or shortest path problems [FFH+ 21]. Given a graph G = (V, E) and an edge e = {u, v} ∈ E, by contracting e we obtain a new graph G′ where u, v are contracted into a new single vertex w, such that w is adjacent to (N (u) ∪ N (v)) \ {u, v}. 8

Let (G, I) be the family of all (G, I)-configurations, for some graph family G and set of strings I. For a predicate P : G × I → {0, 1}, we say that (G, I) ∈ P if P (G, I) = 1. Definition 1. Let (G, I) be a configuration family. Then for t ≥ 1, a t-hop proof labeling scheme (t-PLS) for a predicate P : G × I → {0, 1} is a pair Π = (Prov, Ver) satisfying • Prov, also called the honest prover, is a mapping taking as input a configuration (G, I) ∈ P , and producing a label assignment Prov(G, I) = (ℓ(v))v∈V for all nodes of G, where ℓ(v) ∈ {0, 1}∗ for each v ∈ V . • Ver, also called the verifier, is a function receiving as input the size of the graph |V (G)| = n, and all the information in the t-hop neighborhood of v, including the t-hop topology of v (with the corresponding identifiers), and for each node u ∈ Bt (v), its additional inputs I(u) and label assignments ℓ(u), and outputs a value in {accept, reject} (i.e. accepts or rejects respectively).9 Let Ver(G, I, ℓ, v) denote the output of the function at node v ∈ V , in configuration (G, I), and with labels ℓ = (ℓ(v))v∈V . If Ver accepts, we also allow it to output additional auxiliary values. Additionally, the following holds: • Completeness: for every configuration (G, I) ∈ P and for every node v ∈ V , we have that Ver(G, I, Prov(G, I), v) = accept. • Soundness: for every configuration (G, I) ∈ (G, I) and certificate assignment ℓ = (ℓ(v))v∈V , if Ver(G, I, ℓ, v) = accept for all v ∈ V , then (G, I) ∈ P . We denote the label given to a node v by Prov(G, I) as Prov(G, I, v). The cost of a t-PLS (Prov, Ver) on a configuration (G, I) ∈ P is defined as cost(Prov, G, I) = maxv∈V |Prov(G, I, v)|, i.e. the length of the longest label given to a node by Prov(G, I). The cost of a t-PLS (Prov, Ver) on the configuration family (G, I) is defined by cost(Prov, P, n) = max {cost(Prov, G, I) | (G, I) ∈ P, |V (G)| = n}. Verifier knowledge and additional assumptions: Throughout the paper, we assume that nodes have unique identifiers encoded using O(log n) bits. We further assume that Ver is given access to the size of the graph, i.e., |V (G)| = n, and that the graph is connected. These latter two assumptions are only used in Section B, and we believe they can be removed given some additional technical details, as briefly discussed at the end of that section.

Two-Separated Partitions and Cluster-Degeneracy

In this section, we present two key notions: Two-Separated partitions (TS partitions) and ε-clusterdegeneracy, and relate these notions to obtaining tradeoff theorems. We start by introducing TS partitions, which are our key combinatorial objects whose existence implies the tradeoff theorems. Definition 2 (TS partition). A (t, ε)-Two-Separated partition (TS partition) of a graph G = (V, E) is a pair (C, X) where X ⊆ V , and C is a partition of V , such that: 9

Equivalently, Ver can be seen as a t-round deterministic distributed algorithm with unlimited bandwidth that collects all information in the t-neighborhood of v, and outputs a value in {accept, reject}, and additional output.

• Two separation. ∀C, C ′ ∈ C, every path P = (v1 , . . . , vℓ ) from a vertex in C \ X to a vertex in C ′ \ X has two consecutive vertices in X. That is, for some i ∈ [ℓ − 1], vi , vi+1 ∈ X. • Bounded diameter. ∀C ∈ C, weak-diam(C) ≤ t. We say that a TS partition is connected if every C ∈ C is connected. • The cost ratio of (C, X), defined as R(C, X) = maxi |Ci ∩ X|/|Ci |, holds R(C, X) ≤ ε. Similarly, define for a TS partition (C, X) the cost ratio of a cluster C ∈ C as |C ∩ X|/|C|. Next, we introduce the notion of a decomposition into clusters with ε-cluster-degeneracy, and prove that when combined with low-diameter constraints, the existence of such a decomposition guarantees the existence of a (t, ε)-TS partition. This notion provides a convenient approach for constructing TS partitions in graphs, which we use in both Section 4 and Section 5. Given a ordered partition C = {C1 , . . . , Ck }, a node v ∈ Ci is called a close-to-boundary node if there is a node u ∈ ∪j>i Cj in a cluster with a higher index than i, at distance at most 2. We say that C has ε-cluster-degeneracy if in every cluster Ci , at most ε-fraction of its nodes are close-to-boundary nodes. Definition 3. A partition of V into clusters C = {C1 , . . . , Ck } has ε-cluster-degeneracy if ∀i, v ∈ Ci | distG v, V \ ∪ij=1 Cj ≤ 2 ≤ ε · |Ci |. Lemma 3.1. Assume a graph G = (V, E) has a partition into clusters C = {C1 , . . . , Ck } that has ε-cluster-degeneracy and that is weakly t-bounded. Then G has a (t, ε)-TS partition. Moreover, if all clusters in C are connected, then G has a connected (t, ε)-TS partition. Proof. Let V>i = V \ ∪ij=1 Cj , and V>k = ∅. Setting X = ∪ki=1 (Ci ∩ B2 (V>i )) we argue that (C, X) is a (t, ε)-TS partition, i.e. it fulfills the following three properties: • Diameter and connectivity: By assumption weak-diam(C) ≤ t for all C ∈ C. Additionally, the partition is connected if and only if each C ∈ C is connected. • Cost ratio: We note that Ci ∩ X = Ci ∩ B2 (V>i ), since Ci ∩ B2 (V>i ) ⊆ Ci , and the clusters are disjoint. Therefore, by assumption we have |Ci ∩ X|/|Ci | = |Ci ∩ B2 (V>i )|/|Ci | ≤ ε. • Two Separation: Assume for the sake of contradiction that the two separation property fails. Let Pu,v be the shortest path between two vertices u, v ∈ / X that belong to different clusters C, such that Pu,v does not have two consecutive vertices from X. Denote Pu,v = (w0 = u, w1 , . . . , wℓ−1 , wℓ = v). Let u ∈ Ci , v ∈ Cj where we assume w.l.o.g. that i < j. Since u ∈ / X, we have dist(u, V>i ) > 2, and specifically we have ℓ ≥ 3 and w1 , w2 ∈ / Cj . If w1 ∈ / X, then Pw1 ,v = (w1 , . . . , wℓ = v) contradicts the minimality of Pu,v , thus w1 ∈ X. Similarly, we deduce that w2 ∈ X. Since w1 , w2 ∈ X are consecutive on Pu,v , we obtain a contradiction, and the claim follows.

In the remainder of the section, we show that the existence of (t, ε)-TS partitions implies a tradeoff between O(t)-PLS and 1-PLS. To set this up, we first define the verification task of outputting a (t, ε)-TS partition, in which we both verify the existence of a (t, ε)-TS partition, and have each node locally output nearby clusters and their nodes in X. Definition 4. We say that a t-PLS Π = (Prov, Ver) certifies and outputs a (t, ε)-TS partition if Π is a t-PLS for the existence of a (t, ε)-TS partition in the graph according to Definition 1, and require an additional guarantee: assuming no node rejects for some labeling ℓ, Ver outputs for each node v a set of clusters Comp(v) and a set XC (v) ⊆ V for each C ∈ Comp(v), such that there exists a (t, ε)-TS partition (C, X) of G, satisfying the following properties: (1) Local cluster knowledge. For any node v ∈ V , let Cv ∈ C denote the unique cluster containing v. Then we have for any v ∈ V that Comp(v) = {Cu | u ∈ B2 (Cv )}. In other words, each node v knows Cv and any cluster that is of distance at most two from Cv . (2) Local boundary knowledge. For any v ∈ V , we have XC (v) = X ∩ C for any C ∈ Comp(v). In this case, we refer to (C, X) as the TS partition outputted by the labeling ℓ. Finally, we formalize the relationship between the existence of TS partitions and a tradeoff theorem. Specifically, we show that a (t, ε)-partition that can be outputted with cost c implies that any 1-PLS of cost p can be transformed into an O(t)-PLS with cost O(⌈ε · p⌉ + c). Lemma 3.2 (TS partition implies tradeoff). Let (G, I) be a configuration family. Suppose that for some functions t = t(n) ≥ 1 and ε = ε(n) ∈ [0, 1), every graph G ∈ G with |V (G)| = n admits a (t, ε)-TS partition, and that such a partition can be certified and outputted by an O(t)-PLS with cost c = c(n). Then, for any predicate P on (G, I) and any 1-PLS for P with cost p, there exists an O(t)-PLS for P with cost O(⌈ε · p⌉ + c). Before presenting the proof, we analyze basic properties of TS partitions, and simple lemmas related to certification of P . Then, we discuss efficient encoding and retrieval of information from clusters, which is a crucial part of the prover and verifier algorithms. Basic properties and labeling of (t, ε)-TS partitions We start with a basic claim, that for every node v, there is at most a single cluster C such that B1 (v) (v and its neighborhood) contains non-boundary vertices from C: C \ X. Lemma 3.3. Let (C, X) be a (t, ε)-TS partition. Then for every v ∈ V , there exists a cluster C ∈ C such that B1 (v) ⊆ C ∪ X. In particular, C is unique unless B1 (v) ⊆ X. Proof. Suppose for the sake of contradiction that there is a vertex v such that B1 (v) is not contained in C ∪ X for any C ∈ C (in particular B1 (v) ⊈ X). It follows that there are two neighbors u1 , u2 of v, such that u1 ∈ C1 \ X and u2 ∈ C2 \ X for some clusters C1 ̸= C2 ∈ C. But then (u1 , v, u2 ) is a 2-path connecting C1 \ X and C2 \ X, contradiction to the two separation property. Uniqueness follows from the fact that clusters are disjoint, hence if B1 (v) ⊆ C1 ∪ X and B1 (v) ⊆ C2 ∪ X for some distinct clusters C1 ̸= C2 , then it follows that B1 (v) ⊆ X. Define HC = {v ∈ V | B1 (v) ∩ (C \ X) ̸= ∅}. We have the following two properties of HC . Lemma 3.4. The following two properties hold. 12

(1)

C∈C HC is equal to the set {u | B1 (u) ⊈ X}.

(2) HC ∩ HC ′ = ∅ for any two distinct clusters C, C ′ ∈ C. Proof. We prove the two properties above. (1) This follows trivially from the definition of HC = {v ∈ V | B1 (v) ∩ (C \ X) ̸= ∅}. (2) Let u ∈ HC . Then by Lemma 3.3 we have B1 (u) ∩ (C ′ \ X) = ∅, or in other words u ∈ / HC ′ .

Let Π1 = (Prov1 , Ver1 ) be a 1-PLS for a property P . We introduce two notions for partial labelings related to Π1 which help us certify that (G, I) ∈ P using an O(t)-PLS. Namely, we define some notion of a good labeling of nodes of X (according to Π1 ), and for every C, given a good labeling of nodes of X, we define the notion of a good extension of the good labeling into C \ X. We then show that if there exists a good labeling of X, and a good extension of the labeling into C \ X for every C ∈ C, then (G, I) ∈ P . Definition 5. Let Π1 = (Prov1 , Ver1 ) be a 1-PLS for a property P . Let (C, X) be a (t, ε)-TS partition. We define the following. • We say that a labeling ℓX : X → {0, 1}≤p is a good X-labeling if for all nodes v ∈ X such that B1 (v) ⊆ X, we have Ver1 (G, I, ℓX , v) = accept. • Let ℓX be a good X-labeling. For a cluster C ∈ C, a function ℓC∪X : (C ∪ X) → {0, 1}≤p is called a good extension of ℓX if ℓC∪X (u) = ℓX (u) for every u ∈ X, and for every v ∈ HC we have Ver1 (G, I, ℓC∪X , v) = accept. Lemma 3.5. Let Π1 = (Prov1 , Ver1 ) be a 1-PLS for a property P . Let (C, X) be a (t, ε)-TS partition, and let ℓX : X → {0, 1}≤p be a good X-labeling. If for every cluster C ∈ C there exists a good extension ℓX∪C , then (G, I) ∈ P . Proof. Let ℓX be a good X-labeling, and let ℓC1 ∪X , . . . , ℓCk ∪X be good extensions of ℓX for clusters C1 , . . . , Ck , which exist by the lemma’s assumption. We define a labeling ℓV : V → {0, 1}≤p as follows. ( ℓX (u), u ∈ X, ℓV (u) = ℓC∪X (u), u ∈ C \ X. We argue that Ver1 (G, I, ℓV , u) = accept for all u ∈ V , which implies that (G, I) ∈ P by the soundness of (Prov1 , Ver1 ). We split into two cases - when B1 (u) ⊆ X and otherwise. In the first case, we have by definition of ℓX being good that Ver1 (G, I, ℓV , u) = Ver1 (G, I, ℓX , u) = accept. In the other case, we have by Lemma 3.4 that u ∈ HC for some unique C ∈ C. Therefore, by definition of ℓC∪X being a good extension of ℓX , we get Ver1 (G, I, ℓV , u) = Ver1 (G, I, ℓX∪C , u) = accept. Finally, we discuss how to encode a string across a cluster using node labels, and how to decode it again in order to retrieve the stored information.

Encoding and decoding strings on clusters. As motivated in the introduction, we would like to be able to encode a good ℓX on the labels of the network, where ℓX (v) for v ∈ C ∩ X is encoded using labels of cluster C’s vertices. We first discuss encoding and decoding strings across a cluster, which uses the internal identifier ordering to describe the part numbers of string segments spread across the cluster. Given a cluster C ⊆ V and a string S, we define the lexicographic encoding Lex of S on C as follows. Let k = |C|, and let u1 , . . . , uk be the nodes of C, ordered lexicographically by their node identifiers. Let S ′ = Pad(S, k) be a padding of S so that |S ′ | is divisible by k, and let S1′ , . . . , Sk′ denote the strings obtained by partitioning S ′ into k substrings, each of the same length. For node ui , we define Lex(C, S, ui ) = Si′ .10 Relatedly, we also define a decoding function DecodeLex. Given a cluster C and a labeling ℓ on its vertices such that ℓ(ui ) = Lex(C, S, ui ) for some string S, the function DecodeLex(C, ℓ) reconstructs S by concatenating the labels in lexicographic order and then removing the padding. We are now ready to prove Lemma 3.2. Proof of Lemma 3.2. Given (ProvTS , VerTS ), an O(t)-PLS for computing a (t, ε)-TS partition, and (Prov1 , Ver1 ) a 1-PLS for certifying P , we construct (Provt , Vert ) as follows. We assume w.l.o.g. that the labels given by Provt and received by Vert for each node are of the form (TSLabel, ProofPart) where TSLabel, ProofPart are some strings. If a label breaks this format, Vert rejects in the corresponding node. Description of Provt : Let (C, X) be a (t, ε)-TS partition of the graph that is outputted by ProvTS on the graph G. For a node v, denote Cv as the unique cluster containing v. Let u1 , . . . , uk be the nodes of Cv ∩ X, ordered lexicographically w.r.t. their node identifier, and let XLabel(Cv , X) = (Prov1 (G, I, u1 ), . . . , Prov1 (G, I, uk )). The mapping Provt gives each node v as its label the tuple Provt (G, I, v) = (ProvTS (G, I, v) , Lex(Cv , XLabel(Cv , X), v)) . By the lemma’s assumption, ProvTS (G, I, v) is of size at most c. |XLabel(C, X)| ≤ p · |C ∩ X|. Therefore,

For any C ∈ C we have

| Lex(Cv , XLabel(Cv , X), v)| = O(⌈p · |Cv ∩ X|/|Cv |⌉) = O(⌈p · ε · |Cv |/|Cv |⌉) = O(⌈ε · p⌉). Hence the total cost of Provt is O(⌈ε · p⌉ + c) as required. Description of Vert : Recall we assume that the proof labels of every node v are given in a format encoding two arbitrarily large strings (TSLabel(v), ProofPart(v)) (otherwise we have that node reject). Let TSLabel : V → {0, 1}∗ , ProofPart : V → {0, 1}∗ be the corresponding global functions/labelings. We describe Vert as a distributed algorithm, where we say that a node accepts or rejects corresponding to whether Vert accepts or rejects on this node. In the first step of the verifier we have every node v run VerTS on the labeling TSLabel to certify and output some (t, ε)-TS partition. By the soundness of ΠTS , either a node rejects, or there exists some (t, ε)-TS partition (C, X) satisfying the properties of Definition 4. Assuming no node rejects, 10

We refer back to the string notations in Section 2 for the introduction of Pad and the fixed delimiter scheme.

we fix this partition (C, X). Let Cv denote the unique cluster containing v, and denote for each cluster C ∈ C by leader(C) as the node with the maximum node identifier in C \ X. From the labeling ProofPart we globally define a labeling function ℓX : X → {0, 1}∗ for all nodes in X, in the following manner. Let C ∈ C be a cluster, and let C ∩ X = {u1 , . . . , uk } be the nodes of C ∩ X ordered lexicographically by node id. Then we define, (ℓX (u1 ), . . . , ℓX (uk )) = DecodeLex(C, ProofPart). Node v = leader(C) asserts that DecodeLex(C, ProofPart) does indeed encode k = |C ∩ X| strings, rejecting otherwise. We note that to compute ℓX (v) of any node v ∈ C ∩ X it is sufficient to know the topology of C with its identifiers, and its labels of ProofPart. Therefore, any node v can locally reconstruct for each of C ∈ Comp(v) the labels ℓX (u) of all nodes u ∈ C ∩ X, and specifically for u ∈ B2 (Cv ) ∩ X. Recall the definition of HC = {v | B1 (v) ∩ (C \ X) ̸= ∅}. Every node v performs the following. (1) If B1 (v) ⊆ X (including v), node v asserts that Ver1 (G, I, ℓX , v) = accept. (2) If v = leader(C) for some cluster C ∈ C, node v asserts that there exists a labeling ℓC\X : C \ X → {0, 1}≤p such that the extension ℓC∪X = ℓX ∪ ℓC\X is good, or in other words that ∀u∈HC Ver1 (G, I, ℓC∪X , u) = accept. We note that leader(C) can perform this since in order to check that the extension is good, leader(C) only needs to know ℓX (u) for u ∈ B2 (C) ∩ X. (3) If all assertions passed, node v accepts. Each node checks the assertions above, and accepts if and only if no assertion fails. This concludes the description of Vert . We summarize all assertions made by the verifier in the following list, from the viewpoint of a node v (skipping some in-between steps). (1) Node v runs VerTS on the labeling TSLabel, and rejects if it rejects. Otherwise, it obtains its relevant part in (C, X), i.e. Comp(v) ⊆ C and for each C ∈ Comp(v) a set XC (v). (2) If v = leader(C) for some C ∈ Comp(v), it asserts whether DecodeLex(C, ProofPart) encodes |C ∩ X| many strings (which correspond to (ℓX (u))u∈C∩X ). (3) If B1 (v) ⊆ X (including v), node v asserts that Ver1 (G, I, ℓX , v) = accept. (4) If v = leader(C) for some C ∈ Comp(v), then it asserts that there exists a labeling ℓC\X of C \X such that the extension ℓC∪X = ℓX ∪ℓC\X is good, i.e. that ∀u∈HC Ver1 (G, I, ℓC∪X , u) = accept. Correctness: To show correctness, we assume that a (t, ε)-TS partition exists, and show that Vert (G, I, Provt (G, I), v) = accept, i.e. that all nodes accept given the honest prover labeling. We have that TSLabel(v) = ProvTS (G, I, v), therefore by correctness of (ProvTS , VerTS ) no node rejects, and we have that each node obtains a set Comp(v) ⊆ C and XC for each Comp(v) satisfying the guarantees of Definition 4, passing Assertion (1). Recall the definition of XLabel(C, X) = (Prov1 (G, I, u))u∈C∩X . For each node v, we have that ProofPart(v) = Lex(C, XLabel(Cv , X), v), therefore for each C ∈ Comp(v) we have that DecodeLex(C, ProofPart) = (Prov1 (G, I, u))u∈C∩X .

In particular, we do not reject in Assertion (2), and for every node v ∈ V , we have that it can compute ℓX (u) for all u ∈ C ∩ X. Finally, we show that a node v does not reject in Assertion (3),(4). For Assertion (3), we note that all of u ∈ B1 (v) have ℓX (u) = Prov1 (G, I, u), and therefore v does not reject, by correctness of Prov1 . For Assertion (4), we note that by correctness of Prov1 , we have that ℓX is a good labeling, and hence the labeling ℓC∪X (u) = Prov1 (G, I, u) is a good extension to ℓX , and v = leader(C) accepts. Soundness: Assume that all nodes accept. By Assertion (1),(2) we have some TS partition (C, X) which the nodes collectively hold, and that each cluster C ∈ C encodes |C ∩ X| many strings, corresponding to some labeling (ℓX (u))u∈C∩X . Therefore, the labeling ℓX is well-defined. By Assertion (3), we have that ℓX is a good X-labeling according to Definition 4, and moreover by Assertion (4), we have for each C ∈ C a good extension ℓC∪X . Therefore, by Lemma 3.5, we have that (G, I) ∈ P , and the claim follows.

Tradeoff Theorem for Minor-Free Graphs

In this section, our goal is to prove that the Tradeoff Conjecture holds for Kr -minor free graphs G for any constant r ≥ 1, up to a single additive O(log n) factor. This trivially implies the conjecture for any H-minor free graph family, since it is Kr -minor free as well, for r = |V (H)|. Theorem 1.4. Let r ≥ 1 be a constant, and let (G, I) be a configuration family where G is the family of all Kr -minor free graphs, and let P be a predicate on (G, I). If there exists a 1-PLS for P in (G, I) with cost p, then for any t ≥ 1, there exists a t-PLS for P in (G, I) with cost O(⌈p/t⌉ + log n). On a high level, we show Theorem 1.4 using the existence of a good padded decomposition (introduced next) in G, and relating its existence to the existence of a good TS partition. Then we use the fact that O(log n) is always sufficient for an O(t)-PLS to certify and output a TS partition. Definition 6 (Padded Decomposition). Let G = (V, E) be a graph. A distribution D over partitions of V is a (β, δ, Λ)-padded decomposition if every P ∈ supp(D) is weakly Λ-bounded, and for every 0 ≤ γ ≤ δ and z ∈ V , the ball BγΛ (z) satisfies Pr[BγΛ (z) ⊆ Cz ] ≥ e−βγ (Cz denotes the unique cluster in P containing z). We say that G admits a (β, δ)-padded decomposition scheme if for every Λ > 0, there is a (β, δ, Λ)-padded decomposition for G. We use a result by Conroy and Filtser [CF25], that shows that Kr -minor free graphs have a good padded decomposition. Theorem 4.1 ([CF25]). For any r ≥ 1, every Kr -minor free graph admits an (O(log r), O(1))padded decomposition scheme. Next, we show that having a good padded decomposition implies a good TS partition. First, we show that given an “active” set of nodes L, we can construct a cluster C ⊆ L such that all vertices, other than a O(β/t) fraction, are at least of distance 2 from all other nodes in L. We then use this iteratively to get a partition with O(β/t)-cluster-degeneracy, and conclude the existence of a (t, O(β/t))-TS partition. 16

Lemma 4.2. Let G = (V, E) be a graph that admits a (β, O(1))-padded decomposition scheme. Let L ⊆ V be a set of nodes. Then for any t = Ω(1), there is a cluster C ⊆ L that has weak diameter ≤ t, and such that |C ∩ B2 (L \ C)| ≤ 2β t · |C|. Proof. We sample a partition P = {C1 , . . . , Ck } from a (β, O(1), t)-padded decomposition. Denote Cv the unique cluster containing v. Let Γ2 (L) = {v ∈ L | B2 (v) ⊈ Cv }. We note that Γ2 (L) is precisely the set of second-layer boundary vertices in L across all clusters of P. For every vertex v, it holds that 2β 2β Pr [v ∈ Γ2 (L)] ≤ Pr [B2 (v) ⊈ Cv ] ≤ 1 − e− t ≤ . t Thus by linearity of expectation, E[|Γ2 (L)|] ≤ 2β t · |L|. In particular, there is some partition P 2β where |Γ2 (L)| ≤ t · |L|. Let P be such a partition, and let C be the resulting clusters, and let C ′ = {C ∩ L | C ∈ C}. Let C1′ , . . . , Ck′ denote the non-empty clusters of C ′ . Then the following holds, Pk ′ ′ |Γ2 (L)| |Ci′ ∩ B2 (L \ Ci′ )| 2β i=1 |Ci ∩ B2 (L \ Ci )| ≤ min ≤ ≤ . P ′ k ′ |Ci | |L| t i∈[k] i=1 |Ci | Where the first inequality follows from the mediant inequality.11 Thus taking C = Ci′ as the cluster minimizing the expression on the left-hand side, we found a cluster C as desired. Lemma 4.3. Let G = (V, E) be a graph that admits a (β, O(1))-padded decomposition scheme. Then G has a (t, 2β/t)-TS partition. Proof. Consider the following iterative procedure, where we maintain an active set L, and construct in each step a cluster C ⊆ L using Lemma 4.2, and remove C from L until the set is empty. Initially, set L1 = V . In step i ≥ 1, assume we have a set Li ⊆ V , satisfying |Li | > 0. By Lemma 4.2, there exists a cluster Ci of weak diameter ≤ t, such that |Ci ∩ B2 (Li \ Ci )| ≤ 2β|Ci |/t. Define Li+1 = Li \ Ci . We repeat the process until Li+1 is empty. By a simple induction, we have Li = V \ ∪i−1 j=1 Cj for all i ∈ [k]. Therefore, the set of obtained clusters C = {C1 , . . . , Ck } are a partition of V , having each weak diameter ≤ t, and satisfy ∀i

|Ci ∩ B2 (V \ ∪ij=1 Cj )| |Ci ∩ B2 (Li \ Ci )| = ≤ 2β/t. |Ci | |Ci |

Therefore, C has (2β/t)-cluster-degeneracy, and by Lemma 3.1, G has a (t, 2β/t)-TS partition. By combining Theorem 1.4 and Lemma 4.3, we get the following as corollary. Corollary 4.4. For any r ≥ 1, the family of Kr -minor free graphs has a (t, Θ(log r/t))-TS partition. Next, we show that a (t, ε)-TS partition can always be certified and outputted using an O(t)PLS with cost O(log n). We remark that this lemma is fairly standard, and similar in spirit to prior works (e.g. [FOS21]). Lemma 4.5. In any graph family G and any t(n) ≥ 1, ε(n) ∈ [0, 1) there exists a O(t)-PLS that certifies and outputs a (t(n), ε(n))-TS partition with cost O(log n). 11

Pℓ

i Recall that the mediant inequality states that if a1 , b1 , . . . , aℓ , bℓ > 0 are real numbers, then mini∈[ℓ] abii ≤ Pi=1 . ℓ b i=1

The proof of Lemma 4.5 is deferred to Section A. We are now ready to prove the main theorem. Proof of Theorem 1.4. Recall that by Lemma 3.2, it suffices to show that G has a (t, Θ(1/t))-TS partition, and that it can be certified and outputted by an O(t)-PLS with cost O(log n). The theorem follows immediately by combining Corollary 4.4 and Lemma 4.5. As an immediate corollary, we can obtain a weaker version of Theorem 1.2 for general graphs, which costs an additional logarithmic additive factor, using the following theorem of Bartal. Theorem 4.6 ([Bar96]). Every n-vertex graph admits an (O(log n), O(1))-padded decomposition scheme. Again, by Lemma 3.2 combined with Lemma 4.3, Lemma 4.5 and Theorem 4.6, we obtain the following. Corollary 4.7. Let (G, I) be a configuration family, and P a predicate on (G, I). For G ∈ G with |V (G)| = n, if there exists a 1-PLS for P with cost p, then for any t ≥ 1 there exists an O(t log n)-PLS for P with cost O(⌈p/t⌉ + log n).

Tradeoff Theorem for General Graphs

Our goal in this section is to show a near resolution of the Tradeoff Conjecture in general graphs, up to a single multiplicative logarithmic factor, and with only constant additive factors. In particular, the cost of this scheme converges to a constant number of bits as t grows. Theorem 1.2. Let (G, I) be a configuration family, and P a predicate on (G, I). For G ∈ G with |V (G)| = n, if there exists a 1-PLS for P with cost p, then for any t ≥ 1 there exists an O(t log n)-PLS for P with cost O(⌈p/t⌉).

5.1

Helpful Sequential Algorithm for Finding a (O(t log n), 1/t)-TS Partition

Before proving Theorem 1.2, we describe and analyze a sequential randomized algorithm A on a graph G, which obtains a (O(t log n), 1/t)-TS partition with high probability, and is later used as part of the labeling scheme. For ease of notation, we treat log n as an integer throughout the section, and note that this assumption can be easily removed using appropriate rounding functions. Description of algorithm A: Let v1 , . . . , vn be an ordering of V according to lexicographic order. Initially, we initialize our set of clusters as C = ∅, and the set of active nodes as L1 = V . We iterate over the nodes according to the ordering. In step i ≥ 1, we check whether Li ∩ B2t log n (vi ) = ∅, and if so, we continue to step i + 1. Otherwise, we choose a random even integer ri ∈ {2t log n + 2, 2t log n + 4, . . . , 8t log n}, and define Ci = Bri (vi ) ∩ Li . We note that Ci does not necessarily contain vi , and also might be disconnected. We add Ci to C if |Bri (vi ) ∩ Li | 1 ≤1+ . |Bri −2 (vi ) ∩ Li | t

(1)

If Ci was added to C, we set Li+1 = Li \ Ci , set Xi = Ci ∩ B2 (Li \ Ci ). Otherwise, we set Xi = ∅ and Li+1 = Li . Following this, we continue toSstep i + 1. We conclude at the end of step n, i.e. after the final vertex vn is processed. Let X = ni=1 Xi . We output (C, X) as our TS partition. 18

Analysis of algorithm A: In the analysis, our goal is to show that with some high probability the resulting (C, X) is an (O(t log n), 1/t)-TS partition of G. Specifically, we need to show that C is a partition of V (i.e., every node is assigned to exactly one cluster in C), that the clusters are weakly t-bounded, have cost ratio at most 1/t, and are two separated. We first show that Ln+1 = ∅, which implies that C is a partition. Following this, we show that conditioned that C is a partition, then (C, X) is a (O(t log n), 1/t)-TS partition. We next show that in each step i, if we have some node in Li in the vicinity of vi (i.e. Li ∩ B2t log n (vi ) ̸= ∅), then with some constant probability we create a new cluster in C that contains these nodes. We later argue that since each node has Θ(t log n) nodes in its Θ(t log n)-neighborhood (unless the graph is smaller than Θ(t log n)), then with high probability each node is added to a cluster in some step, and the correctness of the algorithm follows. Lemma 5.1. If at the start of step i we have Li ∩B2t log n (vi ) ̸= ∅, then Eq. (1) holds with probability at least 1/2 over the choice of ri ∈ [2t log n + 2, 8t log n]. Proof. Fix a step i, and denote Badi = {r ∈ {2t log n + 2, 2t log n + 4, . . . , 8t log n} | r does not satisfy Eq. (1) in step i}. Assume by contradiction that | Badi | ≥ t log n + 1, and let {r1′ , . . . , rt′ log n+1 } ⊆ Badi , ordered in ascending order. Therefore, for all j ∈ [2, t log n + 1] we have that 1 1 ′ |Brj′ (vi ) ∩ Li | ≥ (1 + )|Brj′ −2 (vi ) ∩ Li | ≥ (1 + )|Brj−1 (vi ) ∩ Li |, t t where the first inequality holds by definition of Badi , and the second inequality holds due to the ′ fact that we considered only even indices, hence rj−1 ≤ rj′ − 2, and the fact that a ball can only increase in size as the radius grows. By induction on j, we get that 1 1 |Brt′ log n+1 (vi ) ∩ Li | ≥ (1 + )t log n |Br1′ (vi ) ∩ Li | ≥ (1 + )t log n |B2t log n (vi ) ∩ Li | > n, t t where the last inequality follows by the fact (1 + 1/t)t ≥ 2 for any t ≥ 1, and by the lemma’s assumption that |B2t log n (vi ) ∩ Li | ≥ 1. Lemma 5.2. Assume n ≥ 2t log n. Then Pr(Ln+1 ̸= ∅) ≤ 1/n. Proof. We consider a node v and bound the probability of v ∈ Ln+1 . Let S = B2t log n (v), denote k = |S|, and let vi1 , . . . , vik be the vertices of S in lexicographic order. Since we assume n ≥ 2t log n, it is easy to see that k ≥ 2t log n. When processing each vij for j ∈ [k], if v is active in this step (i.e. v ∈ Lij ), then by Lemma 5.1, v is still active at the end of the step (i.e. v ∈ Lij +1 ) with probability at most 1/2. Therefore, Pr(v ∈ Ln+1 ) ≤

k Y

Pr(v ∈ Lij +1 | v ∈ Lij ) ≤ (1/2)k ≤ (1/2)2t log n ≤

j=1

1 . n2

and Pr(Ln+1 ̸= ∅) ≤ 1/n follows by the union bound on all vertices v ∈ V . Next, we show that if C is a partition of V , then it is an (O(t log n), 1/t)-TS partition. 19

Lemma 5.3. If Ln+1 = ∅, then (C, X) is a (16t log n, 1/t)-TS partition. Proof. Recall that if Ci is added to C, then it is non-empty, and that Ci = Bri (vi ) ∩ Li . Since ri ≤ 8t log n, it follows that weak-diam(Ci ) ≤ 16t log n. Next, we show that the cost ratio and two separation conditions hold. The cost ratio follows by:

|Xi | = |Ci ∩ B2 (Li \ Ci )| ≤ |Bri (vi ) ∩ Li | − |Bri −2 (vi ) ∩ Li | 1 ≤ (1 + ) · |Bri −2 (vi ) ∩ Li | − |Bri −2 (vi ) ∩ Li | t |Bri −2 (vi ) ∩ Li | |Ci | = ≤ . t t We note that indeed Xi = Ci ∩ X, since Xi ⊆ Ci and the clusters are disjoint. Finally, we show the two separation property. Assume for the sake of contradiction that the two separation property fails. Let Pu,v be the shortest path between two vertices u, v ∈ / X that belong to different clusters in C such that Pu,v does not have two consecutive vertices from X. By minimality distG (u, v) ≤ 2 (as otherwise we could have taken a shorter path). Let Ci , Cj ∈ C such that u ∈ Ci , v ∈ Cj , and suppose w.l.o.g. that i < j. As distG (u, v) ≤ |Pu,v | ≤ 2, it follows that u ∈ Ci ∩ B2 (Lj ), and thus u ∈ X, a contradiction. Combining Lemma 5.2 and Lemma 5.3, we immediately get the following as a corollary. Corollary 5.4. Assume n ≥ 2t log n. Then (C, X) is a (16t log n, 1/t)-TS partition with probability at least 1 − (1/n). This concludes the description and analysis of A. We call a randomness string R good w.r.t. graph G if by running A using randomness R, we have that the resulting clusters (C, X) are a (16t log n, 1/t)-TS partition. In particular, Corollary 5.4 implies that for any graph G, at least a 1 − (1/n) fraction of the randomness strings are good w.r.t. G. Encoding the randomness string of A and reducing its size: Let us consider the randomness used by A, and its encoding. Naively, we can represent it as a choice of n even indices ri ∈ [2t log n + 2, 8t log n] for each i ∈ [n]. However, in our labeling scheme we run a sort of simulation of A in a distributed manner, where nodes have access to the shared randomness string. The naive representation does not lend itself well to that sort of distributed implementation, as it requires knowledge of the global ordering of node identifiers (i.e., knowing the lexicographic rank of each node u among all identifiers). Instead, we view the randomness as a function that assigns each possible identifier a random index, namely R : [poly(n)] → [2t log n + 2, 8t log n]. With this representation, a node u can locally compute its random index from its identifier alone. The drawback is that describing R explicitly requires poly(n) random bits. We therefore apply a randomness reduction argument to reduce it to O(log n) bits, which we show later can be shared among all nodes using only O(1) label bits.

Let Gn be the family of all graphs of size |V (G)| = n. Next, we prove using a standard argument that for graphs in Gn there exists a set of randomness strings {R1 , . . . , Rn2 } such that for each G ∈ Gn there exists an Ri that is a good randomness string for G.12 Lemma 5.5. For any integer n, there exists a set Fn : [n2 ] → {0, 1}∗ such that for any graph G ∈ Gn there exists an index i ∈ [n2 ] such that Fn (i) is a good randomness string for G. Proof. We notice that algorithm A uses for graphs in Gn at most O(n log n) random bits. Choosing a randomness string R uniformly at random from {0, 1}O(n log n) , we have that for a fixed G ∈ Gn that Pr(R is good randomness for G) ≥ 1 − (1/n). Therefore, if we choose n2 strings R1 , . . . , Rn2 ∈ {0, 1}O(n log n) uniformly at random, we have that 2

Pr(∃i Ri is good randomness for G) ≥ 1 − (1/n)n . By union bound over all graphs in Gn we have that n 2 Pr(∀G∈Gn ∃i Ri is good randomness for G) ≥ 1 − 2( 2 ) · (1/n)n > 0.

Therefore, there exists a set of n2 randomness strings R1 , . . . , Rn2 such that for all G ∈ Gn , there exists an index i ∈ [n2 ] such that Ri is a good randomness string for G. Setting for i ∈ [n2 ] the function Fn (i) = Ri , the claim follows.

5.2

Labeling Scheme for General Graphs

Next, we show how to allow nodes to locally simulate A given O(1)-sized labels. Before showing the labeling scheme, we show for any r ≥ 1 an O(r)-PLS that allows the honest prover to share a string S of size r across all nodes, with cost O(1). Informally, we use this scheme to inform all nodes of an index of a good randomness string for G. Lemma 5.6. Let r ≥ 1 be an integer. Then for any S ∈ {0, 1}r , there exists an O(r)-PLS (Prov, Ver) that uses O(1) bits per node, such that for the honest prover, all nodes output S, and for any other labeling, either all nodes output some shared string S ′ , or at least one node rejects. The proof of Lemma 5.6 is deferred to Section B, and we give a brief sketch of proof. Proof sketch of Lemma 5.6. The key idea of the proof is to show the existence of a vertex set U ⊆ V that splits the graph into connected components C1 , . . . , Ck of G[V \ U ] such that (a) ∀i∈[k] |Ci | = r, and (b) for every v ∈ V there exists i ∈ [k] such that distG (v, Ci ) ≤ r. Given this decomposition, we encode the string S on each of the connected components C1 , . . . , Ck , assigning O(1) bits of S to each node in the component. Therefore, every vertex v can retrieve S from its closest component Ci . Moreover, we can guarantee that, as long as G is connected, all nodes output the same string. To achieve this, we define an auxiliary graph G′ whose vertices correspond to the clusters, and where two clusters are adjacent in G′ if there exists a short path between them in G. We then observe that G′ is connected, meaning that to ensure all nodes output the same string, it suffices to guarantee that neighboring clusters encode the same string. 12 In the literature, this type of argument is often referred to as “Newman’s trick” [New91]. It was originally used in communication complexity to show that public coin protocols can be simulated by private coin protocols, and as a general method to reduce randomness.

We are now ready to prove Theorem 1.2. Let (Provshare , Vershare ) be the labeling scheme for sharing strings described in Lemma 5.6. We construct an O(t)-PLS (Provt , Vert ) as follows. Description of Provt : Let (C, X) be a (t, ε)-TS partition of G. For a randomness string R : [poly(n)] → [2t log n + 2, 8t log n], let TR be the following set: TR = {vi ∈ V | Ci is taken into C when running A using randomness R}. Recall that Lemma 5.5 provides a function Fn : [n2 ] → {0, 1}∗ , such that for any graph in Gn there exists an index i ∈ [n2 ] such that Fn (i) is good randomness for it. Let iG ∈ [n2 ] be a good randomness string for running A in G. Let R∗ = Fn (iG ), let t(v) = 1 if v ∈ TR∗ , and otherwise t(v) = 0, and let x(v) = 1 if v ∈ X, and otherwise x(v) = 0. Denote Shared(iG , v) = Provshare (G, iG , v), the label given by Provshare to node v when sharing the binary encoding of iG to all nodes. The prover gives the following label to each node v ∈ V . Provt (G, I, v) = (Shared(iG , v), t(v), x(v)) . By Lemma 5.6, the cost of Provshare is O(1) bits, and the size of both t(v) and x(v) is a single bit. Therefore in total, the cost of Provt is O(1) bits. Description of Vert : For convenience, we describe the verifier as a distributed algorithm from the viewpoint of v. We assume that the proof labels of any node v are given in a format encoding three strings (ShareLabel(v), InT(v), InX(v)), where InT(v), InX(v) are single bits, and ShareLabel(v) is a constant-sized string. Otherwise we have Vert reject. Before describing the verifier, we define a simple sub-procedure called FindMyCluster(v, R), running from the viewpoint of node v. Node v is given as input a function R : [poly(n)] → [2t log n + 2, 8t log n] mapping every possible identifier to an even index in that range. The subprocedure returns the smallest identifier of a node u ∈ B8t log n (v) satisfying both (a) InT(u) = 1 and (b) distG (u, v) ≤ R(ID(u)). If there is no such node, then v outputs ⊥. Informally, FindMyCluster(v, R) simulates algorithm A from the viewpoint of v, assuming randomness string R, and assuming InT is the set of vertices for which a cluster was taken into C. Its output is the identifier of v’s cluster leader, where ⊥ represents an error. We prove a few simple facts about FindMyCluster. Lemma 5.7. If for nodes u, v ∈ V and some randomness string R we have FindMyCluster(u, R) = FindMyCluster(v, R) ̸= ⊥, then distG (u, v) ≤ 16t log n. Proof. Recall that FindMyCluster is a distributed algorithm that has access to a local neighborhood of radius 8t log n and returns an identifier of some node in this neighborhood. Let w be a node such that ID(w) = FindMyCluster(u, R) = FindMyCluster(v, R). Then necessarily w ∈ B8t log n (u) ∩ B8t log n (v), and by the triangle inequality we have distG (u, v) ≤ distG (u, w)+distG (w, v) ≤ 16t log n. We next formalize the fact that FindMyCluster outputs the lexicographically smallest “taken” center whose ball contains the node.

Lemma 5.8. Fix a randomness string R and labeling InT : V → {0, 1}. For every node u ∈ V , FindMyCluster(u, R) = min {ID(w) | w ∈ B8t log n (u), InT(w) = 1, distG (w, u) ≤ R(ID(w))} , where FindMyCluster(u, R) = ⊥ if the set is empty. Proof. This follows by definition of FindMyCluster, which returns the smallest identifier among nodes satisfying the two conditions above. We are now ready to describe Vert : (1) Node v runs Vershare , using ShareLabel as the labeling and rejects if it rejects. Otherwise, node v obtains some string i′ (v), which it interprets as an encoding of a number. By the soundness of (Provshare , Vershare ), we can assume that unless some node rejects, i′ = i′ (v) is the same for e where all nodes, and omit v from the notation for convenience. Node v computes Fn (i′ ) = R e R : [poly(n)] → [2t log n + 2, 8t log n]. e = ⊥. (2) Node v rejects if FindMyCluster(v, R) e and defines (3) For every node u ∈ B16t log n (v), node v runs FindMyCluster(u, R), ev (v) = {u ∈ B16t log n (v) | FindMyCluster(u, R) e = FindMyCluster(v, R)}. e C ev (v)) it defines Moreover, for any w ∈ B2 (C ew (v) = {u ∈ B16t log n (w) | FindMyCluster(u, R) e = FindMyCluster(w, R)}. e C ew (v) ∈ Comp(v) for every w ∈ B2 (C ev (v)), and defines for each such C ∈ Comp(v) the (4) v adds C set XC = {u ∈ C | InX(u) = 1}. ev (v) has weak diameter ≤ 16t log n, satisfies the cost ratio property, and (5) Node v asserts that C ev (v) \ X e ev (v) with InX(u) = 0 passes through that any path from C to any node u ∈ V \ C Cv (v) at least two consecutive nodes z1 , z2 with InX(z1 ) = InX(z2 ) = 1. Correctness: Assume every node v receives the label Provt (G, I, v). We prove that all nodes accept, and output their corresponding part in the TS partition (C, X) obtained by running algorithm A with randomness string R∗ . Lemma 5.9. Let Cu be the cluster node u belongs to at the end of an execution of algorithm A ev (v) = Cv , and for every u ∈ B2 (Cv ) we have C eu (v) = Cu . with randomness string R∗ . C Proof. Let v1 , . . . , vn be the nodes of the graph, ordered lexicographically. Recall that TR = {vi ∈ V | Ci is taken into C when running A using randomness R}, and that InT(v) = 1 if and only if v ∈ T . We prove by induction on i ≥ 1 that if vi ∈ T , then for all u ∈ Cvi , we have FindMyCluster(u, R∗ ) = ID(vi ). Let us consider the case of i = 1. If v1 ∈ / T, then the claim holds trivially. Otherwise, the algorithm A sets Cv1 = BR∗ (v1 ) (v1 ). Additionally, we have InT(v1 ) = 1, and that v1 is the smallest identifier in the network. Therefore for a node u ∈ V 23

it holds that FindMyCluster(u, R∗ ) = ID(v1 ) if and only if u ∈ BR∗ (v1 ) (v1 ), which completes the basis case. Next, we assume that the induction claim holds for some i ∈ [n − 1], and we prove the claim for i + 1. By the induction assumption, we have that for all j ≤ i that for any u ∈ Cvj that FindMyCluster(u, R∗ ) < ID(vi+1 ). Therefore, the alive set satisfies Li = {u ∈ V | FindMyCluster(u, R∗ ) ≥ ID(vi+1 )}. Again, if vi+1 ∈ / TR∗ , then the claim trivially holds. Otherwise, we have that Cvi+1 is taken into C in algorithm A, and recall that Cvi+1 = BR∗ (vi+1 ) (vi+1 ) ∩ Li . On the other hand, by Lemma 5.8, any node u ∈ Li such that FindMyCluster(u, R∗ ) ≥ ID(vi+1 ) is equivalent to the statement that u does not have a node w ∈ B8t log n (u) such that u ∈ BR∗ (w) (w), and that InT(w) = 1. But since InT(vi+1 ) = 1, then for any u ∈ BR∗ (vi+1 ) (vi+1 ) we have vi+1 ∈ B8t log n (u) , implying that FindMyCluster(u, R∗ ) = ID(vi+1 ). This concludes the proof by induction. ev (v) every C ew (v) for each w ∈ B2 (C ev (v)) are defined The lemma immediately follows, since C by FindMyCluster as ev (v) = {u ∈ B16t log n (v) | FindMyCluster(u, R) e = FindMyCluster(v, R)}, e C and ew (v) = {u ∈ B16t log n (w) | FindMyCluster(u, R) e = FindMyCluster(w, R)}. e C ev (v) = Cv , and C ew (v) = Cw for each w ∈ B2 (Cv ). In other words C Recall that the prover set InX(u) if and only if u ∈ X, or in other words X = {u ∈ V | InX(u) = 1}, therefore it follows that for any C ∈ Comp(v) we have XC (v) = C ∩ X. By the fact that R∗ is a good random string, we are guaranteed that (C, X) is an O((t log n), 1/t)-TS partition, and therefore all clusters satisfy the weak-diameter, cost ratio, and two separation properties. Therefore, all nodes accept, and correctness follows. Soundness: Before proving soundness, we first prove a few simple claims. We define for every w ∈ V the cluster ew = {u ∈ V | FindMyCluster(u, R) e = FindMyCluster(w, R)}. e C ew | w ∈ V }. Additionally, define X e = {w ∈ V | InX(w) = 1} and for each We define Ce = {C e e e e X) e and that C ∈ C define XC = C ∩ X. Our overall goal is to show that the network outputs (C, e e it is indeed an (O(t log n), 1/t)-TS partition. We first show that Cw = Cw (v) for any v ∈ V . ew = C ew (v) assuming C ew (v) is defined by v. Lemma 5.10. For any v, w ∈ V , we have C Proof. Recall that ew (v) = {u ∈ B16t log n (w) | FindMyCluster(u, R) e = FindMyCluster(w, R)}. e C ew (v) ⊆ C ew . We show the other Notice that this definition is completely independent of v. Clearly C e e e direction. Let u ∈ Cw . Then FindMyCluster(u, R) = FindMyCluster(w, R). By Lemma 5.7 we ew (v) and the claim follows. have distG (u, w) ≤ 16t log n, i.e. u ∈ C 24

The following follows as an immediate corollary. ev ∈ Comp(v) and for each Corollary 5.11. Assume all nodes accept. Then for each v ∈ V , C ev ) we have C ew ∈ Comp(v). Moreover, for each C ∈ Comp(v) we have XC (v) = C ∩ X. e w ∈ B2 (C ev (v) = C ev . Therefore C ev ∈ Comp(v) and for each w ∈ B2 (C ev ) Proof. By Lemma 5.10 we have C ew = C ew (v) ∈ Comp(v). The latter claim follows by definition of X e = {u | InX(u) = 1}, we have C and definition of XC (v) = {u ∈ C | InX(u) = 1}. e X) e is an (O(t log n), 1/t)-TS partition of G Finally, we show that the pair (C, eu | u ∈ V } is a partition of Lemma 5.12. Assuming all nodes accept, the family of subsets Ce = {C e X) e is an (O(t log n), 1/t)-TS partition of G. V . Moreover, (C, eu . We show that u appears in exactly one cluster. Indeed, assume Proof. Let u ∈ V . Clearly u ∈ C ew for some w ∈ V . Then by definition we have that u ∈ C e = FindMyCluster(w, R). e FindMyCluster(u, R) eu = C ew . Finally, we show that (C, e X) e is an (O(t log n), 1/t)-TS partition. And it follows that C e ̸= ⊥, and by Step (5) Since u does not reject, then by Step (2) of Vert we have FindMyCluster(u, R) eu (u) satisfies the low diameter, two separation, and cost ratio properties. we have that C e X) e is a (O(t log n), 1/t)-TS partition of G, and We conclude that if all nodes accept, then (C, e for every C ∈ Comp(v), eu | u ∈ B2 (C ev )}, with XC (v) = C ∩ X each node v outputs Comp(v) = {C and soundness follows. By combining this proof labeling scheme with Lemma 3.2, we obtain Theorem 1.2. Discussion on knowledge of n: In this section, we assume the verifier has knowledge of n when locally constructing the function Fn of Lemma 5.5, that is used to obtain our randomness strings. However, we believe this assumption can be removed with relative ease by using the string sharing PLS of Lemma 5.6 to share the value n′ in addition to the index i′ . We note that while n′ might not be the real value of n, we are still guaranteed that the generated randomness string is identical among all nodes. Moreover, since the nodes verify the properties of the resulting TS partition, if they all accept, then the TS partition is valid even if n′ is not the real size of the graph. Once the assumption of knowing n is removed, we can also remove the assumption that the graph is connected, since we can act on each component separately.

Refuting Stronger Variants of the Tradeoff Conjecture

In this section, we refute a stronger variant of the Tradeoff Conjecture, and show a problem where every node has |Bt (v)| = Ω(n), but we cannot get an improvement of better than O(1/t) when considering a t-PLS compared to a 1-PLS. Theorem 1.6. There exists a predicate P on an infinite family of planar graphs G = {Gt,m }∞ t,m=1 and on some auxiliary input set I, where for Gt,m ∈ G we have minv∈V (Gt,m ) |Bt (v)| = Ω(|V (Gt,m )|), and there is a 1-PLS for P with cost O(m), but any t-PLS for P has cost Ω(m/t).

In our proof, we use a reduction to 2-party non-deterministic communication complexity. We begin with a brief overview of the 2-party non-deterministic communication model and the results relevant for our reduction. For simplicity, instead of describing the standard non-deterministic communication model, we describe a slight (but standard) variant. This variant is equivalent to the standard model up to an additive O(1) term in their respective complexity measures. Non-deterministic communication complexity: For our purposes, the non-deterministic 2party communication model consists of two players, Alice and Bob, with private inputs X ∈ X and Y ∈ Y, respectively, for some input domain X × Y. A protocol with cost p in this setting is defined as follows. Initially, both Alice and Bob are given a shared string W ∈ {0, 1}≤p , called the witness string. Without communicating, both Alice and Bob output either accept or reject based solely on their private input and the witness W . For a predicate P : X × Y → {0, 1}, we say that a non-deterministic p-cost protocol solves P if: • Correctness: For any (X, Y ) ∈ X × Y such that P (X, Y ) = 1, there exists a witness string W with |W | ≤ p for which both players accept. • Soundness: For any (X, Y ) ∈ X × Y such that P (X, Y ) = 0, and for every witness string W with |W | ≤ p, at least one of Alice or Bob rejects. We briefly remark that in the standard model, nodes are allowed to communicate, and the cost is the size of W plus the total number of bits communicated. Though, using a standard argument, the difference in cost between the two models is at most two bits. Informally, this is because instead of having lengthy communication, we can always encode the transcript inside W and have both nodes verify the transcript using a single bit each (See [KN97] for an overview). Finally, we describe the equality function and the lower bound needed for our results. The equality function EQk : {0, 1}k × {0, 1}k → {0, 1} is defined by EQk (X, Y ) = 1 if and only if X =Y. Lemma 6.1 ([KN97] Chapter 2.1). Any non-deterministic 2-player protocol solving EQk has cost Ω(k). Proof of Theorem 1.6: Next, we prove Theorem 1.6. We begin by describing Gt,m and P , and continue to show the existence of an O(m) cost 1-PLS for P , and the lower bound of Ω(m/t) on the cost of any t-PLS for P . The graph Gt,m is defined as follows for integer t ≥ 1, and odd integer m ≥ 3. For i ∈ [2t + 3], we define the set of vertices, ( {v i }, i is odd, Vi = i i {v1 , . . . , vm }, i is even. S Let V = i∈[2t+3] Vi be a union of the vertex sets, and note that |V | = Θ(mt). Let Gt,m = (V, E) be a graph where E = {{u, w} | i ∈ [2t+2], u ∈ Vi , w ∈ Vi+1 }, i.e. Gt,m contains for every i ∈ [2t+2] all edges between Vi and Vi+1 (See Figure 2). We define the problem P as follows. In this problem, both nodes v 1 ∈ V1 , v 2t+3 ∈ V2t+3 receive 2 an input I(u) ∈ {0, 1}m . We ignore all additional inputs on nodes not in V1 ∪ V2t+3 , i.e. for nodes with even degree. We define P so that (Gt,m , I) ∈ P if and only if I(v 1 ) = I(v 2t+3 ). Denote deg(v) as the degree of a vertex v. We recall that m is an odd integer, and note the following trivial properties. 26

Lemma 6.2. The following holds for any v ∈ V . 1. If deg(v) = 2, then v is at an even layer. 2. If deg(v) > 2 and is odd, then v ∈ V1 ∪ V2t+3 . Moreover, deg(v) = m. 3. If deg(v) > 2 and is even, then v is at an odd layer, but not in V1 ∪ V2t+3 . Moreover, deg(v) = 2m. Lemma 6.3. There exists a 1-PLS for P in Gt,m with cost O(m). Proof. We describe a 1-PLS for P , denoted (Prov1 , Ver1 ), with cost O(m). Description of Prov1 Let I1 , . . . , Im be a partition of I(v 1 ) into m equal-sized segments. For any j ∈ [2t + 3], if j is odd, then Prov1 (G, I, v) = ϕ, i.e. an empty label. If j is even, then for i ∈ [m], node vij is given the label we set Prov1 (G, I, vij ) = (i, Ii ). We remark that indeed all label sizes are of size at most O(m), hence the cost is at most O(m). Description of Ver1

We define Ver1 as a distributed protocol from the viewpoint of v:

1. If deg(v) = 2 (i.e. v is at an even layer), v accepts. 2. If deg(v) > 2 and is even (i.e. v is at an odd layer, but not in V1 ∪ V2t+3 ), then v sets m = deg(v)/2, and asserts that for each i ∈ [m] there are exactly two labels of neighbors (i1 , S1 ) and (i2 , S2 ) such that i = i1 = i2 and S1 = S2 . 3. If deg(v) > 2 and is odd (i.e. v ∈ V1 ∪ V2t+3 ), v asserts that for each i ∈ [m] there is exactly one label of neighbors (i1 , S1 ) where i = i1 , and that its input is equal to the concatenation of strings I(v) = S1 ◦ · · · ◦ Sm . Correctness We split into cases by layer. Every odd layer vertex always accepts. For each of the layers V1 , V2t+3 we see that indeed for their unique node v, they have m neighbors, each with label (i, Ii ), and indeed I(v) = I1 ◦ · · · ◦ Im . Similarly, for the rest of the odd layers, each node receives for each i ∈ [m] the label (i, Ii ) exactly twice from its neighbors, and we conclude that all nodes accept. Soundness Assume all nodes accept. We prove by induction over all even integers in j ∈ [2t + 3] that for all i ∈ [m] there is exactly one node ui,j ∈ Vj that has the label (i, Ii ). For the case j = 2 this must hold, otherwise v 1 rejects. Assume this for even layer j ≥ 2, therefore layer j + 2 must also have exactly one node ui,j+2 ∈ Vj+2 that has the label (i, Ii ), otherwise v j+1 rejects. Finally, we must have I(v 2t+3 ) = I1 ◦ · · · ◦ Im , otherwise v 2t+3 rejects. We conclude that I(v 1 ) = I(v 2t+3 ). Finally, we show that any t-PLS certifying P in Gt,m has cost Ω(m/t), which is shown by reduction to non-deterministic 2-player equality. Lemma 6.4. Any t-PLS certifying P in Gt,m has cost Ω(m/t).

Proof. Let Πt = (Provt , Vert ) be a t-PLS for certifying P in Gt,m with cost p. We show that this implies a non-deterministic 2-player protocol for (m2 )-bit equality with cost O(p · m · t). Combining with the Ω(m2 ) complexity lower bound on EQm2 (Lemma 6.1), we obtain by rearranging that p = Ω(m/t). We describe a 2-player protocol that uses Πt to obtain the complexity mentioned above. Let X, Y be the private inputs of Alice and Bob respectively. Alice and Bob each construct the graph Gt,m . Alice assigns X to be the input of v 1 , and similarly, Bob assigns Y to be the input of v 2t+3 . Both players interpret W = (ℓ1 , . . . , ℓ|V (G)| ) as a labeling on the nodes V (rejecting if W does not S encode |V (G)| labels). Finally, Alice checks whether all nodes in t+1 i=1 Vi accept, and Bob checks S2t+3 whether all nodes of i=t+2 Vi accept. If so, they accept, and otherwise reject. We analyze the correctness of the protocol above. Assuming X = Y , we show there exists a witness string W causing both players to accept. Indeed, taking W = (Provt (G, I, v))v∈V , and noting that X = Y implies I(v 1 ) = I(v 2t+3 ), then by correctness of Πt all nodes accept. Otherwise, assume that X ̸= Y , i.e. I(v 1 ) ̸= I(v 2t+3 ). Therefore, by the soundness of Πt , for any S labeling ℓ : VS→ {0, 1}∗ the verifier Vert rejects on at least one node v. We note that either v ∈ t+1 i=1 Vi or 2t+3 v ∈ i=t+2 Vi . In the first case, Alice rejects, and in the latter Bob rejects.

Acknowledgments This work is supported in part by the Israel Science Foundation, grant No. 1042/22 and 800/22.

References [ACF+ 23] Virginia Ardévol Martı́nez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi, and Jean-Florent Raymond. A lower bound for constant-size local certification. Theoretical Computer Science, 971:114068, 2023. 1 [Bar96]

Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193, 1996. 6, 7, 18

[BFP24]

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local certification of graph decompositions and applications to minor-free classes. Journal of Parallel and Distributed Computing, 193:104954, 2024. 2

[BFZ25]

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local certification of local properties: Tight bounds, trade-offs, and new parameters. SIAM J. Discret. Math., 39(4):1974–2002, 2025. 1

[CF25]

Jonathan Conroy and Arnold Filtser. How to protect yourself from threatening skeletons: Optimal padded decompositions for minor-free graphs. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2281–2292. ACM, 2025. 6, 16

[CHPP20] Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112–124, 2020. 2 28

[CKM25]

Linda Cook, Eun Jung Kim, and Tomáš Masařı́k. A tight meta-theorem for local certification of mso2 properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 110–120, 2025. 2

[FBP22]

Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of mso properties in tree-like graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, page 131–140, New York, NY, USA, 2022. Association for Computing Machinery. 2

[Feu21]

Laurent Feuilloley. Introduction to local certification. Discret. Math. Theor. Comput. Sci., 23(3), 2021. 1, 2

[FF16]

Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bull. EATCS, 119, 2016. 2

[FFH+ 21] Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in distributed proofs. Distributed Comput., 34(2):113–132, 2021. 1, 2, 3, 7, 9 [FFM+ 21] Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83(7):2215–2244, 2021. 2, 5 [FJKS24] Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišt’an, and Josef Erik Sedláček. Decreasing verification radius in local certification. In International Symposium on Algorithmics of Wireless Networks, pages 188–201. Springer, 2024. 1 [FMRT24] Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A metatheorem for distributed certification. Algorithmica, 86(2):585–612, 2024. 2 [FOS21]

Orr Fischer, Rotem Oshman, and Dana Shamir. Explicit space-time tradeoffs for proof labeling schemes in graphs with small separators. In 25th International Conference on Principles of Distributed Systems (OPODIS), volume 217 of LIPIcs, pages 21:1–21:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 1, 2, 3, 7, 17

[GS16]

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory Comput., 12(1):1–33, 2016. 2, 5

[KK07]

Amos Korman and Shay Kutten. Distributed verification of minimum spanning trees. Distributed Comput., 20(4):253–266, 2007. 2, 5, 9

[KKP10]

Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Comput., 22(4):215–233, 2010. 1, 2, 5

[KN97]

Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. 26

[New91]

Ilan Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39(2):67–71, 1991. 21

[OPR17]

Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In International Colloquium on Structural Information and Communication Complexity, pages 53–70. Springer, 2017. 1, 7

[Suo13]

Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1–24:40, 2013. 2

Missing Proofs from Section 4

In this section, we prove Lemma 4.5. Namely, we show that any (t, ε)-TS partition can be certified and outputted in any graph using a O(t)-PLS with cost O(log n). Lemma 4.5. In any graph family G and any t(n) ≥ 1, ε(n) ∈ [0, 1) there exists a O(t)-PLS that certifies and outputs a (t(n), ε(n))-TS partition with cost O(log n). Let r = 3t+2. We construct an r-PLS (Prov, Ver) certifying and outputting a (t, ε)-TS partition as follows. Description of Prov: Let (C, X) be a (t, ε)-TS partition of G. For each cluster C ∈ C, the honest prover assigns a unique identifier ID(C) ∈ [n], and gives node v the label Prov(G, I, v) = (ID(Cv ), x(v)), where x(v) is a single bit set to x(v) = 1 if v ∈ X, and x(v) = 0 otherwise. We note that the size of the label for each node is O(log n) bits. Description of Ver: For convenience, we describe Ver as a distributed algorithm running from the viewpoint of node v. We assume that v receives for every node u ∈ Br (v) a label (CompID(u), InX(u)), where InX(u) is a single bit (otherwise v rejects). Given the r-hop topology of v, node v defines ev (v) = {w ∈ Br (v) | CompID(v) = CompID(w)}, C ev (v)) defines the cluster and for each u ∈ B2 (C eu (v) = {w ∈ Br (u) | CompID(u) = CompID(w)}. C eu (v) | u ∈ B2 (C ev (v))}, and for each C ∈ Comp(v) defines the set It then defines Comp(v) = {C XC (v) = {w ∈ C | InX(w) = 1}. Node v asserts the following conditions, and rejects if at least one assertion fails. (1) Node v asserts that for each C ∈ Comp(v) that weak-diam(C) ≤ t, and the cost ratio is at most |XC (v)|/|C| ≤ ε. ev (v) and w ∈ ev (v), with InX(u) = InX(w) = (2) Node v asserts that there are no two nodes u ∈ C /C 0, such that distG (u, w) ≤ 2. If all assertions are true, then Ver accepts and outputs Comp(v), and for each C ∈ Comp(v) outputs the set XC (v) as its corresponding X-set. This concludes the description of the verifier. 30

Correctness: Since (C, X) is a (t, ε)-TS partition, and each C ∈ C is given a distinct identifier, eu (v) = Cu . Moreover, for ev (v) = Cv , and for any u ∈ B2 (Cv ), it similarly holds that C then C e each u ∈ B2 (Cv ), the cluster Cu (v) = Cu satisfies the weak-diameter, two separation, and cost ratio conditions. Therefore, all assertions of Ver running on v are true, and it accepts and outputs Comp(v) = {Cu | u ∈ B2 (Cv )}, and for each C ∈ Comp(v) the set XC (v) = XC . Soundness: Assume that for every node v ∈ V , Ver accepts for some labeling ℓ. We begin by showing a few simple claims. ev (v), then CompID(u) ̸= CompID(v). Lemma A.1. If u ∈ Br (v), and u ∈ /C ev (v) = {w ∈ Br (v) | CompID(w) = CompID(v)}. Hence, if u ∈ Br (v) and Proof. By definition, C ev (v), then necessarily CompID(u) ̸= CompID(v). u∈ /C ew (u) ∈ Comp(u) and C ew (v) ∈ Lemma A.2. Assume all nodes accept. For any u, v, w ∈ V , if C ew (u) = C ew (v). Moreover, in that case X e (u) = X e (v). Comp(v), then C Cw Cw ew (v) \ C ew (u). Since z ∈ C ew (v), by Proof. Assume by contradiction that there exists a node z ∈ C ew (u) definition we have z ∈ Br (w) and CompID(z) = CompID(w). On the other hand, since z ∈ /C e while CompID(z) = CompID(w), again by definition of Cw (u) it must be that z ∈ / Br (w), a e e contradiction. Therefore Cw (v) = Cw (u). ew Moreover, the corresponding sets XCew (u) and XCew (v), defined as the set of vertices y ∈ C with InX(y) = 1, are equal as well. eu (v) are consistent Lemma A.2 shows that given a labeling ℓ where all nodes accept, the clusters C eu = C eu (u), and X e = whenever they are defined. In the remainder of the section, we denote C Cu eu (u) ∈ Comp(u). We XCeu (u). We note that this is defined for all u ∈ V , since we always have C eu | u ∈ V }, and X e = S X e . We show that (C, e X) e is an (t, ε)-TS partition. let Ce = {C Cu eu | u ∈ V } is a partition of Lemma A.3. Assuming all nodes accept, the family of subsets Ce = {C e e V . Moreover, (C, X) is an (t, ε)-TS partition of G. Proof. To show that Ce is a partition, we show that every node appears in some cluster, and that any two clusters that the clusters are disjoint. The fact that every u ∈ V appears in some cluster eu and C eu ∈ C. e follows from u ∈ C e e eu ∈ Assume that z ∈ Cu ∩ Cv . Then CompID(u) = CompID(z) = CompID(v). Since C e e Comp(u) and Cv ∈ Comp(v), both u and v accept Assertion (1), and hence weak-diam(Cu ) ≤ t ev ) ≤ t. It follows that distG (u, v) ≤ 2t. We claim that C eu = C ev . Indeed, let and weak-diam(C e eu ) ≤ t, we y ∈ Cu . Then CompID(y) = CompID(u) = CompID(v). Moreover, since weak-diam(C have distG (u, y) ≤ t, and thus by the triangle inequality distG (v, y) ≤ distG (v, u) + distG (u, y) ≤ ev . The 2t + t = 3t ≤ r. Therefore y ∈ Br (v) and has the same component identifier as v, i.e., y ∈ C e e e e symmetric argument shows Cv ⊆ Cu , concluding Cu = Cv . ev have the weak We conclude that since every node passes Assertions (1),(2), then all clusters C e e is a (t, ε)-TS diameter, cost ratio, and two separation properties. In other words, the pair (C, X) partition. e X), e and Lemma 4.5 Finally, we show that all nodes output their respective local part of (C, follows. 31

ev ∈ Comp(v) and for each Lemma A.4. Assume all nodes accept. Then for each v ∈ V , C e e e u ∈ B2 (Cv ) we have Cu ∈ Comp(v). Moreover, for each C ∈ Comp(v) we have XC (v) = C ∩ X. ev = C ev (v) and indeed is defined by v and added to Comp(v). Therefore, Proof. By definition C e e ev ) a cluster C eu (v) and adds it to B2 (Cv ) = B2 (Cv (v)). In particular, v defines for any u ∈ B2 (C e e Comp(v). By Lemma A.2, we have Cu (v) = Cu , and the first part of the claim follows. ev ) such For latter claim, let C ∈ Comp(v). By definition of Comp(v), there exists u ∈ B2 (C e e e that C = Cu (v). By Lemma A.2, C = Cu and moreover XC (v) = XCeu . Since C is a partition of V eu ∩ X e = C ∩ X. e (Lemma A.3), we have X e = C Cu

Missing Proofs from Section 5

In this section, we prove Lemma 5.6. We start by first proving the following decomposition lemma. Lemma B.1. Let r ≥ 1 be an integer parameter, and let G = (V, E) be a connected graph with |V | > r. There exists a vertex set U ⊆ V that satisfies the following properties. Let C1 , . . . , Ck be the connected components of G[V \ U ]. Then, (a) For every i ∈ [k], |Ci | = r, and (b) For every v ∈ V , there exists i ∈ [k] such that v ∈ Br (Ci ). Proof. We use the following simple iterative procedure to construct the set U and clusters C1 , . . . , Ck , proving this decomposition’s existence. At each step we have our set of active nodes Vi , initially set at V1 = V . At the i-th step, if there is no connected component remaining in the graph with size at least r, we terminate the process. Otherwise, set Ci to be an arbitrary connected subgraph of such a component, of size exactly r, and let Ui = {u ∈ Vi \ Ci | u ∈ B1 (Ci )}. We set Vi+1 = Vi \ (Ci ∪ Ui ). Assuming the process ended at step k + 1, we set U = Vk+1 ∪ Next we prove correctness of this process.

j=1 Uj .

• Property (a) follows trivially from the fact that each cluster is taken to be a connected subgraph of size exactly r. • For Property (b), we consider a few simple cases. If v ∈ Ci ∪ Ui for some i ∈ [k], then v ∈ B1 (Ci ). Otherwise, v ∈ Vk+1 , i.e. v is one of the nodes remaining at the end of the process. Since k + 1 is the last step, the connected component of v in Vk+1 is of size at most r − 1. In particular, distG (v, ∪ki=1 Ui ) ≤ r − 1, implying v ∈ Br (Ci ) for some i ∈ [k].

Next, we show an implication of Property Lemma B.1(b), which we use for the soundness of the protocol. For an integer parameter r ≥ 1, and set U ⊆ V , define the graph G′ (r, U ) as follows. Let C1 , . . . , Ck be the maximal connected components of G[V \ U ]. Let G′ (r, U ) be the graph with vertices V ′ = {v1′ , . . . , vk′ }, such that two vertices vi′ , vj′ ∈ V ′ are connected by an edge if and only if distG (Ci , Cj ) ≤ 2r + 1. Lemma B.2. Let r ≥ 1 be an integer parameter, let G = (V, E) be a connected graph, and let U ⊆ V . If maxv∈V distG (v, V \ U ) ≤ r, then G′ (r, U ) is connected. 32

Proof. Consider a path p = (w1 = u, w2 , w3 , . . . , wℓ = v) between two nodes u, v ∈ V \ U . For j ∈ [ℓ], let Cij denote the maximal connected component in G[V \ U ] closest to wj in G (breaking ties arbitrarily). By assumption, distG (wj , Cij ) ≤ r. It follows by the triangle inequality that distG (Cij , Cij+1 ) ≤ 2r + 1, i.e. vi′j is connected by an edge to vi′j+1 in G′ (r, U ), for all 1 ≤ j ≤ ℓ − 1. Hence, vi′ , vj′ are connected in G′ (r, U ) if there is a path between the connected components Ci and Cj in G. Since G is connected, we conclude that G′ (r, U ) is also connected. Before the proof of Lemma 5.6, recall the functions Lex and DecodeLex for encoding and decoding strings across a cluster C that were introduced in Section 3. In short, Lex(C, S, v) pads S to a multiple of |C|, and returns the i-th block, where i is the lexicographic rank of v in C. Conversely, DecodeLex(C, ℓ), where ℓ(v) = Lex(C, S, v) for v ∈ C, reconstructs the original string S by concatenating these blocks in order and removing the padding. Proof of Lemma 5.6 We show a (4r + 2)-PLS for the problem described. We assume that the labeling given to a node v is of the form (InU(v), PartS(v)), where InU(v) ∈ {0, 1} is one bit and PartS(v) ∈ {0, 1}∗ is an arbitrary string (otherwise, the verifier rejects). Given a labeling (InU, PartS) on all nodes, let V0 = {v ∈ V | InU(v) = 0}. A 0-cluster C ⊆ V is a maximal connected component in G[V0 ], i.e. a maximal connected component in the graph induced by nodes with InU(v) = 0. Description of Prov: Fix a set U ⊆ V satisfying the properties described in Lemma B.1. Set Prov as a function which gives labels (InU(v), PartS(v)) to each node v, where (a) Set InU(v) = 1 if v ∈ U , and InU(v) = 0 otherwise. (b) If v ∈ U , set PartS(v) = ∅. Otherwise, let Cv be the 0-cluster that contains v, and set PartS(v) = Lex(Cv , S, v). Description of Ver: We describe the verifier from the viewpoint of v, and say that node v rejects if Ver(G, I, v) = reject, and node v accepts otherwise. First, v rejects if its label is not in the format (InU(v), PartS(v)) with InU(v) ∈ {0, 1}. Let SeenClusters(v) = {C ⊆ B4r+1 (v) | C is a 0-cluster}. Node v rejects if |SeenClusters(v)| = 0, if minC∈SeenClusters(v) distG (v, C) > r, or if there is a 0cluster C such that distG (v, C) ≤ r, but such that |C| ̸= r. Then v runs for all C ∈ SeenClusters(v) the function DecodeLex(C, PartS) and obtains a string ′ S (C). It then asserts that for all C, C ′ ∈ SeenClusters(v) we have S ′ (C) = S ′ (C ′ ). If this assertion is false, v rejects. Otherwise, there is some string S ′ = S ′ (C) for all 0-clusters C ∈ SeenClusters(v). v accepts and outputs the string S ′ . Correctness: We need to show that Ver(G, I, Prov(G, I), v) accepts for all v ∈ V , and that all nodes output the string S. By Lemma B.1(b) there exists a 0-cluster C such that distG (v, C) ≤ r, and in particular C ⊆ B4r+1 (v), so |SeenClusters(v)| ≥ 1 and minC ′ ∈SeenClusters(v) distG (v, C ′ ) ≤ r. Let C ∈ SeenClusters(v). We note that for any u ∈ C we have PartS(u) = Lex(C, S, u). Therefore, DecodeLex(C, PartS) = S, i.e. S ′ (C) = S for all C ∈ SeenClusters(v). Correctness follows. Soundness: Assume that all nodes v ∈ V accept on some labeling ℓ = (InU, PartS). Let U (ℓ) = {v ∈ V | InU(v) = 1}. We show that the following holds. Lemma B.3. If Ver(G, I, v) = accept for all v ∈ V , then:

(1) The cluster graph G′ (r, U (ℓ)) is connected. (2) For any 0-cluster C, we have that |C| = r. (3) Let C, C ′ be 0-clusters that are connected by an edge in G′ (r, U (ℓ)), then S ′ (C) = S ′ (C ′ ). Proof. We show that indeed all the properties above hold. (1) Since every node v accepts, it holds that minC∈SeenClusters(v) distG (v, C) ≤ r. In particular distG (v, V \U (ℓ)) ≤ r for all v ∈ V , and hence by Lemma B.2 the graph G′ (r, U (ℓ)) is connected. (2) Let v ∈ C, then C ∈ SeenClusters(v) (otherwise v rejects). This implies that |C| = r, since v asserts that |C| = r for every C ∈ SeenClusters(v). (3) Since C, C ′ are connected by an edge, then by definition distG (C, C ′ ) ≤ 2r + 1, and by (2) we have |C| = r. Therefore, for a vertex v ∈ C we have that C, C ′ ⊆ B4r+1 (v). In particular, C, C ′ ∈ SeenClusters(v) and v asserts that S ′ (C) = S ′ (C ′ ). The lemma implies that there exists some string S ′ , such that for every 0-cluster C, S ′ (C) = S ′ . This follows from the cluster graph G′ (r, U (ℓ)) being connected, and that for every edge {C, C ′ } ∈ E(G′ (r, U (ℓ))) we have that S ′ (C) = S ′ (C ′ ). Moreover, since for any v ∈ V , we have |SeenClusters(v)| ≥ 1 (otherwise v rejects), then node v outputs the string S ′ , and soundness follows.

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