PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Jelani Nelson, Huacheng Yu

arXiv:1807.05135v3cs.DScs.CC

TL;DR

The paper studies the space and communication required to compute spanning forests in fully dynamic and distributed settings. It proves lower bounds matching the AGM sketch’s upper bounds, while leaving the distributed low-failure regime open.

  • Problem

    The paper asks how much memory or communication spanning forest computation requires when edges can be dynamically inserted and deleted or vertices communicate neighborhood-based sketches to a referee.

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

  • Method

    The paper proves lower bounds for fully dynamic data structures and distributed sketching protocols, using reductions and communication-protocol arguments.

    Source: §1 · p. 2, §3 · p. 6, §4.1 · p. 12

  • Results

    Ω(n log(n/δ) log^2 n) bits are necessary for fully dynamic spanning forest in the stated δ range, and distributed protocols need average message length Ω(log^3 n) even at arbitrarily small constant success probability.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The lower bounds match the AGM sketch’s upper-bound orders for the fully dynamic and constant-success distributed settings.

    Source: §1 · p. 2

    Extending the distributed sketching lower bound to the low-failure regime remains open.

    Source: §1 · p. 3

Abstract

from arXiv · show

We show optimal lower bounds for spanning forest computation in two different models: * One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $\epsilon>0$. We prove that any such data structure must use $\Omega(n\log^3 n)$ bits of memory. * There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $\epsilon>0$. We prove the average message length must be $\Omega(\log^3 n)$ bits. Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability $1 - 1/\mathrm{poly}(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $\delta$, as long as $\delta > 2^{-n^{1-\epsilon}}$.

1 Introduction

The introduction asks for optimal lower bounds for fully dynamic and distributed spanning forest computation, where earlier work provided matching AGM sketch upper bounds but little lower-bound progress. It establishes lower bounds in both models and identifies a low-failure extension that remains open for the distributed model.

1 Introduction

  • Ω(n log(n/δ) log^2 n) bits are necessary for fully dynamic spanning forest when δ lies in the stated range, matching the AGM sketch’s upper-bound order.The lower bound applies for 2^-n^(1-ε) < δ < 1-ε, for any fixed positive ε.Source: §1 · p. 2
  • The fully dynamic lower bound is nearly the strongest possible in its failure-probability range because exact edge storage achieves zero failure below δ=2^-n.The lower bound is stated for δ > 2^-n^(1-ε), up to 1-ε.Source: §1 · p. 2
  • For distributed sketching, even arbitrarily small constant success probability requires average message length Ω(log^3 n).The AGM sketch gives a protocol with maximum message length O(log^3 n) bits and failure probability 1/poly(n).Source: §1 · p. 2
  • Extending the distributed sketching lower bound to the low-failure regime remains open; the authors conjecture a bound of Ω(log(n/δ) log^2 n) for δ > 2^-n^(1-ε).Source: §1 · p. 3

2 Proof Overview

Both lower bounds are reduced to the one-way public-coin communication complexity of UR⊂. The distributed lower bound uses two reductions, while the dynamic data-structure lower bound adapts direct-product reasoning to obtain the needed space bound.

2 Proof Overview

  • The proof strategy starts from the public-coin one-way complexity of UR⊂, where Bob must find an element in S \ T.The lower bound of [KNP+17] supplies the communication hardness used by both reductions.Source: §2 · p. 3

2.1 Distributed sketching lower bound

  • The distributed lower bound first transfers an n-vertex protocol to smaller graph instances, then reduces UR⊂ to graph sketching.The UR⊂ reduction encodes T as neighbors in a private block and S \ T as neighbors in Vr, allowing a spanning forest to reveal an element of S \ T.Source: §2.1 · pp. 3–4

2.2 Data structure space lower bound

  • The dynamic-space argument reduces n-fold UR⊂ to fully dynamic spanning forest and needs a direct-product bound beyond prior black-box theorems.The cited theorems impose unsuitable communication limits, and some alternatives allow constant-probability aborts, which weaken the UR⊂ bound.Source: §2.2 · pp. 4–6

3 Distributed Sketching Lower Bound

The distributed sketching lower bound reduces spanning-forest protocols to UR⊂ communication. Independent graph copies lower the per-instance error, and a constructed graph makes a spanning forest reveal an element of S \ T.

Reduction to smaller graphs

  • Independent disconnected copies reduce the problem to n^4/5-vertex instances with error O(n^-1/5) and expected average message length O(L).Because messages depend only on local neighborhoods, the copies remain independent after conditioning on their messages.Source: §3 · pp. 6–7

Reduction from UR⊂

  • A one-way UR⊂ protocol derived from the sketching protocol has error O(L^1/2 · n^-1/5) and communication cost O(L).The construction handles expected average message length by mixing the hard graph distribution with two distributions that bound message lengths for Vm and Vr.Source: §3 · pp. 7, 11
  • The hard graph makes any spanning forest reveal an edge from vi to Vr, which encodes an element of S \ T.T corresponds to vi's neighbors in Vi, while S \ T corresponds to its neighbors in Vr.Source: §3 · pp. 8–9
  • The other vertices' sketches are controlled by bounding how much Vr's messages reveal about the chosen vi's neighborhood.The reduction uses the condition that |Vr| · L is much smaller than |Vm| to limit that information.Source: §3 · pp. 8–9

Theorem 1

  • L ≥ Ω(log^3 n): any randomized distributed spanning-forest protocol with success probability ǫ requires this expected average sketch size.The argument transfers sketching cost to UR⊂, whose communication lower bound yields the result.Source: §3 · pp. 6, 7, 11

4 Fully Dynamic Spanning Forest Data Structure

Section 4 proves fully dynamic spanning-forest space lower bounds by reducing the data-structure problem to n-fold UR⊂ communication, then deriving that communication bound through a direct-product lemma and a one-fold information lower bound.

4 Fully Dynamic Spanning Forest Data Structure

  • Theorem 3 establishes a space lower bound for fully dynamic spanning forest throughout the stated failure-probability range, δ ∈ [2^-n^(1-ε), 1-ε].The range holds for any fixed constant ε > 0.Source: §4 · p. 12

4.1 Reduction to n-fold UR⊂

  • A C-bit fully dynamic spanning-forest data structure on 2n nodes yields a C-bit protocol for n-fold UR⊂ over [n].Alice inserts edges corresponding to S_i and sends the data structure's memory; Bob deletes edges corresponding to T_i, then uses the forest to find neighbors in S_i \ T_i.Source: §4.1 · p. 12

4.3 n-fold UR⊂lower bound

  • Lemma 2 establishes an n-fold UR⊂ communication lower bound over its stated failure range, using a one-fold reduction and an information lower bound robust to distribution shifts.Lemma 5 requires bounded marginal KL divergences and small conditional KL divergences from its fixed hard distribution.Source: §4.1 · p. 12, §4.3 · p. 18

4.2 Direct product lemma

  • Lemma 3 reduces an n-fold protocol to a one-fold protocol by selecting a coordinate and conditioning on other coordinates and correctness.The resulting protocol has internal information cost O(C/n).Source: §4.2 · p. 13

A The AGM sketch for small failure probability

The AGM sketch is adjusted to support arbitrarily small failure probability by changing its parameters. Its space bound is optimal, and the same construction gives a distributed protocol with bounded message length.

A The AGM sketch for small failure probability

  • For k ≥ 1 and 0 < δ1, δ2 < 1, support-finding may fail with probability at most δ1, return arbitrary output with probability at most δ2, and otherwise return up to k elements from support(z).A solution uses O((t log n + log(n/δ2)) log(n/t)) bits of memory, and its memory contents can be represented as a linear sketch Πz for some matrix Π.Source: A The AGM sketch for small failure… · p. 20
  • Changing δ′ and the number of rounds R is the only algorithmic difference from the original AGM sketch, whose δ′ was 1/10.For δ ≥ 1/poly(n), the original analysis already applies.Source: A The AGM sketch for small failure… · pp. 19–20
  • The query algorithm runs R rounds, using vertex sketches to find edges leaving components and merge non-maximal components into a forest.Each component's signed edge-incidence vector has support exactly on its outgoing edges, so a support-finding query can return a merge edge.Source: A The AGM sketch for small failure… · p. 21
  • At least ⌈log_(3/2) n⌉ good rounds suffice for a spanning forest, and the chosen R and δ′ make the probability of too few good rounds at most δ/2.A good round reduces the number of non-maximal components by a factor of at least 2/3; the per-round bad probability is at most 3δ′.Source: A The AGM sketch for small failure… · p. 21
  • O(n log(n/δ) log^2 n) bits of space suffice for success probability 1 − δ, and the theorem states this bound for the AGM sketch.The bound is optimal for δ > 1/2n^(1−Ω(1)).Source: A The AGM sketch for small failure… · pp. 19, 22
  • O(log(n/δ) log^2 n) bits per vertex suffice as a maximum message length in the distributed model with shared public randomness.Each vertex can send the memory contents of its sketches to the referee, who runs the query algorithm.Source: A The AGM sketch for small failure… · p. 22

B Proof of Lemma 5

The proof uses a randomized encoding of a random set: it reconstructs the set while limiting the information revealed by the encoding. Its analysis controls the behavior of an adaptive sequence of queries.

B Proof of Lemma 5

  • The encoding samples T0, writes a protocol message M, uses shared randomness, and then records round outputs and a residual set.The encoder begins with S drawn from D′[S], and the decoder is designed to reconstruct S.Source: B Proof of Lemma 5 · p. 22
  • The decoder reconstructs S from the encoding, so H(S | Enc(S), π) = 0.The analysis bounds the information revealed by the encoding, including contributions from T0, M, round bits, and the residual-set description.Source: B Proof of Lemma 5 · p. 23
  • For a random T drawn from Dur[T | S], the protocol output lies in S \ T with probability at least 1 − O(δ).This claim supports using the message M, generated for (S, T0), on later inputs T.Source: B Proof of Lemma 5 · p. 24
  • The later-round set T is not necessarily uniform because earlier correct outputs are retained, but the proof bounds how far its point probabilities can increase.The process adds random subsets, sometimes conditioned to include a previous output; the stated claim bounds the increase by a factor involving δ.Source: B Proof of Lemma 5 · p. 24
  • Under the stated δ range, the expected number of successful additions is Ω(R), yielding an information-cost lower bound in the proof.The argument first obtains this expectation for a constant-probability set of S values and uses nonnegativity of |A|.Source: B Proof of Lemma 5 · p. 25

Related papers

Loading 1807.05135v3…