PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction

Peter Robinson, Ming Ming Tan

arXiv:2609.05795v1cs.DScs.DC

TL;DR

Existing lower-bound techniques do not yield stronger results for connectivity and spanning-tree sketching at much smaller error probabilities. The paper analyzes hard graph constructions to establish polynomial lower bounds in the tiny-error regime and extends its results to k-edge connectivity.

  • Problem

    Earlier lower bounds for connectivity and spanning-tree sketching do not strengthen for significantly smaller error probabilities, leaving tiny-error lower bounds unresolved.

    Source: §1 · p. 2

  • Method

    The proof uses graph constructions in which center-node messages must distinguish alternatives, rather than reducing from a communication-complexity problem.

    Source: §1.3 · pp. 3–4

  • Results

    The paper establishes polynomial lower bounds for tiny-error connectivity and spanning-tree algorithms and an Ω_ε(n^ε) bound for subpolynomial k-edge connectivity.

    Source: §1.2 · pp. 2–3

  • Takeaways & Limitations

    The results take a step toward resolving the tiny-error lower-bound question that prior techniques could not address.

    Source: §1 · p. 2

    For larger error probabilities, the proof yields only the known Θ(log^3 n) threshold and no useful stronger bound.

    Source: §1 · p. 2, §1.2 · p. 3

Abstract

from arXiv · show

We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $\Theta( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $\delta$ requires messages of length $\Omega( \min\{n, \log_2 \frac{1}{\delta}\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $\Omega( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $\Theta( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $\Omega( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $\Omega_\epsilon( n^{\epsilon} )$ bits, for any constant $\epsilon<\tfrac{1}{3}$.

1 Introduction

The introduction frames tiny-error connectivity and spanning-tree sketching as an open lower-bound challenge and presents polynomial lower bounds that include deterministic algorithms. It outlines the model, technical approach, related work, and extensions to k-edge connectivity.

1.1 Preliminaries: Sketching Model and Graph Problems

  • Each node sends one message containing a sketch of its neighborhood to a referee who has no prior graph information; sending all neighbor IDs costs linear message length.The referee outputs a spanning tree, a connectivity bit, or whether every nontrivial cut has at least k edges.Source: §1 · p. 1, §1.1 · p. 2

1.2 Our Contributions

  • The paper establishes polynomial lower bounds for tiny-error connectivity and spanning-tree algorithms, including deterministic algorithms; for larger errors, its proof yields only the known Θ(log^3 n) threshold.The authors describe these as the first polynomial lower bounds in this regime.Source: §1.2 · pp. 2–3
  • For subpolynomial k, the message length is Ω_{α,ε}(n^ε) bits for every fixed ε < 1/3, improving on Robinson and Tan’s deterministic-algorithm Ω(k) bound.Source: §1.2 · p. 3

1.3 Technical Challenges and Our Approach

  • Because each edge is shared by its endpoints, vertex partitioning obstructs direct communication-complexity reductions; earlier simulations add roughly 1/n^ε error and do not handle tiny-error bounds.The earlier simulation approach is attributed to [NY19] [Yu21].Source: §1.3 · pp. 3–4
  • The proof uses ordered balanced splits of neighbor IDs: bounding the 3-ary VC dimension limits safe splits, and dangerous triples help show center messages cannot distinguish alternatives needed for a correct spanning tree.The construction samples center, private-neighbor, and shared-neighbor sets; the correct tree depends on a sampled binary vector.Source: §1.3 · p. 4

1.4 Additional Related Work

  • Earlier work established deterministic hardness for other graph problems [BMN+11], randomness separations, and sketching bounds for MIS and spanning trees.The introduction also relates graph sketching to single-round broadcast congested clique and summarizes prior round-complexity results.Source: §1.4 · p. 5

1.5 Roadmap

  • The paper develops OBS bounds, defines a hard input distribution, analyzes dangerous triples and transcript error, proves the connectivity and spanning-tree results, then extends them to k-edge connectivity.The randomized main result is completed using Yao’s lemma.Source: §1.5 · p. 5

2 Ordered Balanced Splits

The section uses ordered balanced splits (OBSs) to capture how a node’s message function distinguishes neighbor sets. It bounds the complexity and prevalence of safe OBSs, supporting the later hard-input construction.

2 Ordered Balanced Splits

  • An ordered balanced split (OBS) partitions a 3q-element universe into P, R0, and R1, each of size q.Source: §2 · p. 6
  • Safety captures whether the message function distinguishes the input pairs needed for the referee to compute the answer.Source: §2 · p. 6
  • For a B-bit message function, the family of safe OBSs has 3-ary VC dimension at most 2B + 3.Source: §2 · p. 7
  • A uniformly sampled OBS is safe for a fixed message function with probability at most 2^-q.Source: §2 · p. 8

3 The Hard Input Graph Distribution

The section samples graph instances using a shared random partition, per-center neighbor choices, a binary vector, and an independent index. The spanning-tree and connectivity graphs differ in their special edges, encoding different answer-relevant properties.

3 The Hard Input Graph Distribution

  • The hard distribution samples an ordered partition, then per-center subsets, a uniform binary vector X, and an independent uniform index J.Source: §3 · p. 9
  • The spanning-tree graph adds the hub edge {h0, h1}, whereas the connectivity graph instead adds {h0, sJ}.Source: §3 · p. 10
  • Distinct binary vectors yield spanning-tree graphs with no common spanning tree.Source: §3 · p. 10
  • The connectivity graph is connected if and only if XJ = 1.Source: §3 · p. 10

4 Unsafe and Dangerous Splits

The section defines unsafe OBSs and dangerous triples to identify when message functions fail to distinguish inputs. Conditioning on these events constrains which messages can reveal the sampled binary vector.

4 Unsafe and Dangerous Splits

  • With probability at least 1 - q^2·2^-q, all center OBSs are unsafe, by the bound on the chance that any sampled OBS is safe.Source: §4 · p. 11
  • For a center whose OBS is unsafe, a sampled triple is dangerous with probability at least 2^-3q, so all M = q^2 centers have dangerous triples with probability at least 2^-3q^3.Source: §4 · p. 11
  • Conditioned on all triples being dangerous, center nodes send the same message across binary vectors, leaving the right-side transcript as the only messages that may depend on X.Source: §4 · p. 12
  • The right-side transcript has at most 2^(2qB) possible values.Source: §4 · p. 12

5 The Distributional Error of Spanning Tree Construction

The section bounds spanning-tree construction error under the hard distribution by conditioning on dangerous and unsafe events. Its argument uses the fact that correct outputs must distinguish binary vectors, while only a limited transcript can depend on those vectors.

5 The Distributional Error of Spanning Tree Construction

  • The section combines the conditional failure bound with the probabilities of All-Dangerous and All-Unsafe to bound distributional error.Source: §5 · p. 13
  • Conditioned on All-Dangerous and All-Unsafe, spanning-tree construction fails with probability at least 1/2.Source: §5 · p. 13
  • Correct spanning-tree outputs for distinct binary vectors require distinct right-side transcripts, because only those messages can depend on the vector.Source: §5 · pp. 12–13

6 The Distributional Error of Connectivity Testing

The connectivity lower-bound argument converts the sketch into decoders for bits of a random vector, then bounds their error under the hard distribution. Even after conditioning on the stated partition, triples, and events, the failure probability over X and J is at least 1/4.

6 The Distributional Error of Connectivity Testing

  • The argument fixes J and the fixed messages to form deterministic decoders whose output is the sketching algorithm’s connectivity decision.The correct decision is identified with X_J, turning connectivity testing into recovery of a bit of X.Source: §6 · p. 13
  • A random-access inequality relates the error of these decoders to their encoding of a uniformly random binary vector.The inequality is stated for deterministic encoding, decoders indexed by J, and uniform independent J; its error parameter is Pr[g_J(Z) ≠ X_J].Source: §6 · p. 13
  • At least 1/4 of the remaining X,J choices cause failure, conditioned on the partition, sampled triples, All-Dangerous, and All-Unsafe.The section applies this conditional bound in a subsequent probability estimate.Source: §6 · p. 14

7 Completing the Proof of Theorem 1

The proof completes the connectivity lower bound by applying the distributional result to the hard input distribution and invoking Yao’s minimax lemma. The spanning-tree result follows by an analogous argument using its corresponding distributional lemma.

7 Completing the Proof of Theorem 1

  • The theorem applies to connectivity and spanning-tree construction when error is at most δ ≤ 1/n^log8 n.Its stated conclusion is a worst-case message-length lower bound; the displayed passage truncates before giving the bound.Source: §7 · p. 14
  • The proof pads the hard-distribution graphs with isolated padding vertices when needed to obtain n-node inputs.It first ensures the hard distributions are supported on graphs of the required size.Source: §7 · p. 15
  • The proof obtains B = Ω(q) for connectivity by combining the distributional error bound with Yao’s minimax lemma and contradicting the assumed error probability.The spanning-tree proof is analogous, using Lemma 12 instead of Lemma 15.Source: §7 · pp. 14–15

8 Extension to k-Edge Connectivity

A blow-up construction reduces connectivity to k-edge connectivity by replacing each node with a clique and each edge with a complete bipartite graph between clusters. The construction preserves connectivity exactly as k-edge connectivity.

8 Extension to k-Edge Connectivity

  • The section extends the connectivity lower bound to k-edge connectivity through the blow-up reduction.The text also treats exponentially small error, but the supplied passage does not show the resulting bound.Source: §8 · pp. 15–16
  • Each node of H is replaced by a clique on its cluster, and each edge becomes a complete bipartite graph between the corresponding clusters.The partition of [n] into clusters is selected before constructing B_k(H).Source: §8 · p. 15
  • H is connected if and only if its blow-up B_k(H) is k-edge connected.The proof considers cuts that split a cluster and cuts that are unions of complete clusters.Source: §8 · p. 16
  • The simulated connectivity protocol concatenates the messages of the simulated nodes, using up to 2(k+1)B bits per original node.Applying the connectivity lower bound to this simulation yields a lower bound on the original message length.Source: §8 · p. 16

9 AI Disclosure

The authors disclose GPT 5.5’s role in suggesting a theorem application and the blow-up simulation, while stating that the authors wrote and verified the paper’s content.

9 AI Disclosure

  • GPT 5.5 suggested using [KM78] for a VC-dimension bound and the blow-up simulation; the authors say no AI-generated text was included.The authors state they wrote and verified all content, including the lemmas, theorems, and proofs.Source: §9 · p. 17

A Proof of Lemma 13

Lemma 13 considers a uniform random bit vector encoded deterministically and decoded by deterministic binary decoders. Its proof notes that, given the encoding, each bit and its corresponding error variable determine one another.

Loading 2609.05795v1…