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

Arnold Filtser, Orr Fischer · 2026

Read Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes by Arnold Filtser, Orr Fischer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19078.txt.

Introduction

Arnold Filtser and Orr Fischer nearly resolve the tradeoff conjecture for proof labeling schemes, which certify network properties. A prover labels each node; each node accepts or rejects from its labelled t-hop neighbourhood. Cost is max label size. The conjecture claims a 1-proof scheme of cost p implies a t-proof scheme of cost about p divided by t. The authors prove this up to one logarithmic factor in general graphs, and up to an added logarithmic term for fixed minor-free graphs. They refute a stronger variant.

Catalog record

CREATORArnold Filtser, Orr Fischer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115693
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.19078

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes Arnold Filtser, Orr Fischer Abstract In the t t -Proof Labeling Scheme model ( t t -PLS model), our goal is to certify that a network of nodes satisfies a given property P P . A prover assigns a label to each node, and each node decides to accept or reject based on its labeled t t -hop neighborhood. If P P holds, there exists a labeling that makes all nodes accept. If P 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 1 -PLS for a property P P with cost p p implies the existence of a t t -PLS for P P with cost O ⁡ ( ⌈ p / t ⌉ ) O(\lceil p/t\rceil) . The conjecture was initially shown to hold for specific graph classes, such as trees, cycles, and grids. Later, a weaker O ~ ​ ( ⌈ Δ ​ p / t ⌉ ) \widetilde{O}(\lceil\Delta p/\sqrt{t}\rceil) cost was shown for fixed minor-free graphs, where Δ \Delta 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 1 -PLS with cost p p implies the existence of an O ⁡ ( t ​ log ⁡ n ) O(t\log{n}) -PLS with cost O ⁡ ( ⌈ p / t ⌉ ) O(\lceil p/t\rceil) for the same property. For fixed minor-free graphs (which include e.g. planar graphs), we show that the existence of a 1 1 -PLS with cost p p implies the existence of a t t -PLS with cost O ⁡ ( ⌈ p / t ⌉ + log ⁡ n ) O(\lceil p/t\rceil+\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 t -hop neighborhoods is an insufficient condition for obtaining a tradeoff better than O ⁡ ( ⌈ p / t ⌉ ) O(\lceil p/t\rceil) . 1 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 [ 17 ] , 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 [ 13 ] 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 \Pi=(\mathrm{Prov},\mathrm{Ver}) , where \mathrm{Prov} is a prover strategy that assigns a label to each node, and \mathrm{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 \mathrm{Prov} . • Soundness: if (G,I) does not satisfy P , then for every labeling at least one node rejects. The cost of a scheme \Pi is the maximum label size assigned by the prover \mathrm{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 [ 21 ] , MST and shortest path problems [ 9 ] , colorings [ 1 , 12 ] , and dominating sets [ 12 ] . On the other hand, some works investigated space-time tradeoffs of any property P [ 21 , 9 , 14 , 4 ] . The focus of our work is on this latter category. The t -PLS model was first defined by Ostrovsky, Perry, and Rosenbaum [ 21 ] , who showed that any property P can be certified by a t -PLS with cost O(\min(n^{2},m\log{n})/t) . Following this work, Feuilloley, Fraigniaud, Hirvonen, Paz, and Perry [ 9 ] 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(\lceil p/t\rceil) . 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 [ 14 , 1 , 12 , 4 ] and the survey [ 13 ] . Conjecture 1.1 (The Tradeoff Conjecture [ 9 ] ) . If there exists a 1 -PLS for a predicate P on all graphs with cost p=p(n) , then for any t\geq 1 , there exists a t -PLS for P with cost O(\lceil p/t\rceil) . We resolve the weak version of the conjecture (mentioned as Problem 1 in [ 9 ] ). 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 (\mathcal{G},\mathcal{I}) is a pair consisting of a graph family \mathcal{G} and a set of possible auxiliary inputs \mathcal{I} . Theorem 1.2 . Let (\mathcal{G},\mathcal{I}) be a configuration family, and P a predicate on (\mathcal{G},\mathcal{I}) . For G\in\mathcal{G} with |V(G)|=n , if there exists a 1 -PLS for P with cost p , then for any t\geq 1 there exists an O(t\log{n}) -PLS for P with cost O(\lceil p/t\rceil) . Consider the problem of MST verification in graphs with integer polynomial edge weights. Kutten and Peleg [ 18 ] constructed a 1 -PLS with cost O(\log^{2}{n}) . Later, Feuilloley et al. [ 9 ] constructed a t -PLS with cost O(\lceil\log^{2}{n}/t\rceil) . However, their t -PLS can only be applied for t=O(\log n) . Thus, the scheme of [ 9 ] has cost \Omega(\log n) even for very large t . By applying our black-box Theorem 1.2 combined with [ 18 ] , we get a general tradeoff, and an improvement over [ 9 ] for the parameter range t\geq\log^{2}n . In particular, for t=\Omega(\log^{3}n) , we get constant cost. Corollary 1.3 ( t -PLS for MST verification) . For any t\geq\log{n} , there exists a t -PLS for the MST verification problem with cost O(\lceil\log^{3}{n}/t\rceil) . Next, we prove that the Tradeoff Conjecture holds in fixed minor-free graphs, up to a single additive

Read the complete text