PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Distributed Sketching Lower Bound for Connectivity

Huacheng Yu

arXiv:2007.12323v1cs.DScs.DC

TL;DR

The paper studies how much distributed sketching communication is needed to decide graph connectivity, a one-bit task with a prior lower bound for the harder spanning-forest output. It reduces connectivity to a communication problem and proves an expected average sketch-size lower bound of Ω(log^3 n), matching the AGM upper bound.

  • Problem

    Prior work gave an Ω(log^3 n) sketch-size lower bound for outputting a spanning forest, while connectivity asks only whether the graph is connected.

    Source: §1 · p. 2

  • Method

    The paper constructs a graph from blocks whose connectivity encodes the XOR of block cases, then reduces connectivity to UR⊂dec.

    Source: §2.2 · p. 7

  • Results

    With success probability at least 3/4, the expected average sketch size for deciding connectivity is at least Ω(log^3 n) bits.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Connectivity decision requires the same Ω(log^3 n) lower-bound scale previously established for spanning-forest computation.

    Source: §1 · p. 2

    The paper says it is unclear whether its new technique extends to streaming connectivity.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an $n$-node graph $G$ is distributed to $n$ players such that each player sees the neighborhood of one vertex. The players then simultaneously send one message to the referee, who must compute some function of $G$ with high probability. For connectivity, the referee must output whether $G$ is connected. The goal is to minimize the message lengths. Such sketching schemes are equivalent to one-round protocols in the broadcast congested clique model. We prove that the expected average message length must be at least $\Omega(\log^3 n)$ bits, if the error probability is at most $1/4$. It matches the upper bound obtained by the AGM sketch [AGM12], which even allows the referee to output a spanning forest of $G$ with probability $1-1/\mathrm{poly}\, n$. Our lower bound strengthens the previous $\Omega(\log^3 n)$ lower bound for spanning forest computation [NY19]. Hence, it implies that connectivity, a decision problem, is as hard as its "search" version in this model.

1 Introduction

This section introduces distributed graph sketching and its connectivity problem, then presents an Ω(log^3 n) average-message lower bound that matches the AGM sketch’s upper bound. It also situates the result among related distributed-computing work and summarizes the AGM sketch and paper organization.

1 Introduction

  • Distributed graph sketching gives each of n players one vertex neighborhood, then has them send sketches to a referee who decides whether the graph is connected.The model seeks to minimize message lengths and corresponds to one-round broadcast congested clique protocols.Source: §1 · p. 2, §1.1 · p. 2
  • With error at most 1/4, deciding connectivity requires expected average sketch size Ω(log^3 n) bits.This strengthens the prior Ω(log^3 n) lower bound for outputting a spanning forest, despite connectivity requiring only one bit.Source: §1 · p. 2

1.1 Related work

  • The related-work overview connects sketching to BCAST(b) and UCAST(b), noting prior broadcast algorithms and that the new result gives a nontrivial connectivity lower bound for b=ω(log n).The overview also describes streaming connectivity and notes that extending the paper’s technique to streaming is unclear.Source: §1.1 · pp. 2–3

1.2 AGM sketch

  • The AGM sketch uses mergeable neighborhood hashes to recover outgoing edges from vertices or connected components, enabling the referee to determine connectivity.It samples edges across O(log n) levels, uses O(log^2 n)-bit hashes and O(log n) instances, for O(log^3 n)-bit messages.Source: §1.2 · pp. 3–4

1.3 Organization

  • The paper previews lower-bound overviews in Section 2, a UR⊂dec communication lower bound in Section 3, and the main theorem in Section 4.The section sequence is stated in the introduction.Source: §1.3 · p. 4

2 Overview

The overview presents a lower-bound reduction from a decision version of universal relation to connectivity, alongside the earlier spanning-forest reduction. Its central technical challenge is proving that the decision version remains hard despite Bob receiving a partition of the universe.

2 Overview

  • The overview introduces UR⊂dec as a decision variant of universal relation and states that it is as hard as the search version.Bob receives a partition of [U] \ T promised to contain all of S \ T on one side, and must determine which side.Source: §2 · p. 5

2.1 Previous reduction from UR⊂

  • The previous spanning-forest reduction uses many potential vertices and a much smaller set of other endpoints to limit information leakage from shared edges.Under its stated parameters, the UR⊂ lower bound yields an Ω(log^3 n) lower bound for spanning-forest computation.Source: §2.1 · pp. 5–6

2.2 Overview of our reduction

  • Connectivity of the linked graph encodes the XOR of √n block cases, reducing connectivity to UR⊂dec with U = n^Θ(1) and δ = 1/n^Θ(1).For most blocks, success on the whole-graph XOR with probability 3/4 implies the referee can identify the block case with probability 1 − O(1/√n).Source: §2.2 · p. 7

2.3 Universal relation lower bound

  • Earlier UR⊂ lower bounds reconstruct elements from Alice’s message by repeatedly simulating Bob, using random mixing to manage error across rounds.The overview reports an optimal communication bound of Θ(log^3 n) for U = n^Θ(1) and δ = n^−Θ(1).Source: §2 · p. 5, §2.3 · p. 8

2.4 Lower bound for decision version

  • The decision-version lower bound analyzes what Alice’s message reveals without supplying Bob’s valid partition, then uses a structural lemma to support the reconstruction argument.The lemma guarantees a set S* whose intersection of size k occurs in at least an exp(−Θ(k)) fraction of the input sets.Source: §2.4 · pp. 8–9

3 Lower Bound for UR⊂

The section constructs a hard input distribution for UR⊂ and analyzes a random process used to establish its communication lower bound. The process’s failure probability is bounded under a specified range of error probabilities.

3 Lower Bound for UR⊂

  • For exp(−U^1/4) < δ < 1/log^4 U, Lemma 5 asserts a lower bound on expected communication for protocols solving UR⊂ under a hard input distribution.The supplied passage does not include the bound’s value.Source: §3 · p. 10
  • Alice’s set has one uniformly chosen element from each of m=U^1/3 blocks, while Bob receives a random subset T of size t_r and a partition placing S\T wholly in one part.The construction selects r uniformly from {0,…,R−1}; its validity requires δ > exp(−U^1/4) and sufficiently large U.Source: §3 · p. 10
  • The process builds nested families S_i and growing sets T_i, using intersections outside T_i to enlarge T_i while shrinking the family less than by a factor B^k_i.Random blocks are sampled to support later rounds; the process stops when |T_i| reaches R or aborts.Source: §3 · pp. 10–11

3.1 Failure probability of A

  • For exp(−U^1/4) < δ < 1/log^4 U, the probability that process A fails is at most 1/2.The failure analysis bounds bad rounds and sums their probabilities over the rounds.Source: §3 · p. 11, §3.1 · p. 14

4 Sketch Size Lower Bound

The section proves an Ω(log^3 n) lower bound on expected average sketch size for deciding connectivity with error at most 1/4, first analyzing a one-block problem and then extending the bound to all vertices using randomized block constructions.

4 Sketch Size Lower Bound

  • Error at most 1/4 requires expected average sketch size Ω(log^3 n) for distributed connectivity sketches.This is Theorem 1, restated in the section.Source: §4 · p. 18
  • Connectivity is encoded as the XOR of block bits; an embedding transfers the one-block lower bound to the full graph.The proof selects a block with small expected average sketch size and simulates the connectivity protocol to decide whether s1 connects to t1 or t2.Source: §4 · pp. 18–20

4.1 Sketch size lower bound for one block

  • The one-block hard instance embeds a UR⊂dec instance so that deciding whether s1 connects to t1 or t2 reveals which partition contains S \ T.The block has two connected components, with t1 and t2 in different components; its construction uses matched vertex sets and corresponding neighborhoods.Source: §4.1 · pp. 20–22
  • For exp(−U^1/4) < δ < 1/log^4 U, the UR⊂dec distribution requires expected one-way communication Ω(log(1/δ) log^2 U) for success probability at least 1 − δ.For the section’s parameter setting, this bound is Ω(log^3 n).Source: §4.1 · p. 21
  • When L ≤ n^1/16, the one-block argument yields protocol error at most 4n^-1/32, so Lemma 5 forces L = Ω(log^3 n).It bounds how much conditioning on the sketches of ±V_r changes the posterior over a sampled vertex’s neighborhood, using a mutual-information bound.Source: §4.1 · pp. 23–24

4.2 Extending to average sketch size

  • The extension’s block construction always has two connected components, with s1, s2 in different components and t1, t2 in different components.Its randomized procedures create blocks in which constant fractions of vertices have neighborhoods distributed like those in ±V_m or ±V_r.Source: §4.2 · pp. 24–25
  • For expected average sketch size over all vertices, Lemma 9 gives L = Ω(log^3 n) by reducing to the one-block lower bound.The extension bounds the expected average sketch sizes of ±V_m and ±V_r by O(L), using construction procedures in which a constant fraction of vertices have neighborhoods distributed like those sets.Source: §4.2 · p. 25

Related papers

Loading 2007.12323v1…