PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling Nondeterministic Communication Complexity of Graph Connectivity

Zhijun Zhang

arXiv:2610.32346v1cs.CC

TL;DR

The communication complexity of graph connectivity remained open for nondeterministic and randomized protocols beyond known lower bounds. This paper analyzes rectangle sizes and proves optimal nondeterministic complexity, alongside error- and round-dependent randomized lower bounds.

  • Problem

    The optimal nondeterministic and randomized communication complexities of graph connectivity remained unresolved, despite an O(N log N) deterministic protocol and an Ω(N) randomized lower bound.

    Source: §1 · p. 3

  • Method

    The paper bounds 1-monochromatic rectangle sizes and extends the analysis to weighted rectangles that are nearly 1-monochromatic, using a shortcutting reduction for the connectivity proof.

    Source: §2.1 · p. 7, §7.2 · p. 36

  • Results

    Nondeterministic graph connectivity complexity is Θ(N log N), while randomized complexity is Ω(N · log(min(1/ε, N))) and, with constant error, Ω(N/r · log N) for r rounds.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    The randomized error-dependent bound is optimal for polynomially small error, and the constant-error round tradeoff is optimal for every constant number of rounds.

    Source: §1.1 · p. 4

    The auxiliary lower-bound result applies for r ≪ n; substantially stronger bounds remain unclear with current techniques when rounds are far fewer than layers.

    Source: §1.1 · pp. 4–5

Abstract

from arXiv · show

Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic protocols by Hajnal, Maass, and Tur\'an [STOC'88], the optimal nondeterministic and randomized complexities have remained unresolved for decades. We settle the nondeterministic communication complexity of graph connectivity by proving an optimal $\Omega(N\log N)$ lower bound. The best prior bound was $\Omega(N\log\log N)$ due to Raz and Spieker [Combinatorica'95]. Our bound is shown by upper bounding the maximum size of $1$-monochromatic rectangles. Generalizing our techniques to weighted, almost $1$-monochromatic rectangles yields an $\Omega(N \cdot \log(\min(1/\varepsilon,N)))$ lower bound for randomized protocols with error probability $\varepsilon$. In particular, this bound is optimal for any polynomially small $\varepsilon$. For constant error probability, we also prove that any $r$-round protocol requires $\Omega(N/r \cdot \log N)$ communication, which is optimal for every constant $r$. Previously, optimal $\Omega(N\log N)$ lower bounds for graph connectivity were known only for $1$-round [Sun, Woodruff; APPROX/RANDOM'15] and $2$-round protocols [Radhakrishnan, Reddy, Venkat; ITCS'26]. Our proof introduces a new communication problem which can be viewed as a composition of inner product and pointer chasing problems. Our lower bounds can be extended to other fundamental graph properties, and also imply optimality of known query and streaming algorithms for related problems.

1 Introduction

Graph connectivity has an O(N log N) deterministic protocol, but its nondeterministic and randomized communication complexities had remained unresolved. The paper settles the nondeterministic bound and establishes error- and round-dependent randomized lower bounds, with consequences for other graph properties and algorithms.

1 Introduction

  • The introduction situates connectivity among communication-complexity work on matching, coloring, cuts, vertex covers, and planarity.It also notes established connections to streaming, sketching, query algorithms, and quantum communication.Source: §1 · p. 3, §1.2 · p. 6

1.1 Our Results

  • The nondeterministic communication complexity of N-vertex graph connectivity is Θ(N log N), matching the spanning-forest protocol’s O(N log N) deterministic communication scale.The prior nondeterministic lower bound was Ω(N log log N).Source: §1.1 · p. 3, §1 · p. 3
  • For nondeterministic lower bounds, the proof bounds maximum 1-monochromatic rectangle size; randomized bounds use weighted rectangles that are nearly 1-monochromatic.Shortcutting three alternating edges reduces a Hamiltonian cycle to a smaller instance for the rectangle analysis.Source: §1.1 · p. 4
  • For error probability ε, randomized graph connectivity requires Ω(N · log(min(1/ε, N))) communication, which is optimal when ε = 1/poly(N).For ε = o(1), the bound is superlinear, improving the earlier Ω(N) lower bound.Source: §1 · p. 3, §1.1 · p. 4
  • With constant error, r-round protocols require Ω(N/r · log N) communication, yielding optimal Ω(N log N) bounds for every constant r.Earlier optimal bounds covered 1-round and 2-round protocols.Source: §1 · p. 3, §1.1 · p. 4
  • The proof introduces IP◦PCn,r, composing inner product with pointer chasing across r permutation layers, and proves an Ω(n log n) randomized lower bound for r ≪ n.Protocols must chase the input bits through the permutation layers before computing the final inner product.Source: §1.1 · pp. 4–5
  • The connectivity lower bounds extend to bipartiteness, cycle-freeness, Eulerian, Hamiltonian, and planarity testing, and imply optimality for related query and streaming algorithms.The zero-error cut-query algorithm for connectivity has optimal expected Θ(N) query complexity; constant-pass global minimum-cut streaming requires Ω(N log N) space.Source: §1.1 · p. 5

1.2 Related Work

  • Earlier pointer-chasing work studied round-limited protocols and permutation variants, while prior graph-connectivity results established optimal randomized bounds for one and two rounds.For constant r ≥ 3, prior work gave an Ω(N log(2r+1) N) lower bound.Source: §1 · p. 3, §1.2 · p. 5

2 Technical Overview

The overview proves the nondeterministic lower bound by bounding 1-monochromatic rectangles, then extends the approach to randomized protocols and introduces a composed problem for constant-error lower bounds. It also explains how the new problem addresses a round-efficient pointer-chasing protocol that complicates earlier approaches.

2.1 Nondeterministic Lower Bound

  • The proof directly upper bounds the logarithmic size of all 1-monochromatic rectangles, rather than only projections of a special collection as in.The overview contrasts this with the earlier argument, which bounded projections onto a coordinate under an additional rectangle assumption.Source: §2.1 · p. 7
  • Shortcutting three alternating edges reduces a Hamiltonian cycle to a smaller instance, allowing rectangle analysis to recurse on n−1.After fixing A(u)=v, the remaining randomness in B must be bounded; the overview identifies this as the key step beyond the shortcut.Source: §2.1 · p. 7
  • The shortcut multiplicity is constrained by cyclic order: many valid vertices require triples to share an order across every a in A.The overview links this restriction to a bound on the remaining randomness in B, obtained through an edge-coloring argument.Source: §2.1 · pp. 7–8
  • The weighted, almost 1-monochromatic rectangle extension yields optimal Ω(n log n) lower bounds for polynomially small error probabilities.The additional loss in this extension comes from bounding the remaining randomness in B.Source: §2.1 · p. 8

2.2 Randomized Lower Bound with Constant Error

  • Round-efficient protocols for earlier pointer-chasing variants make them unfavorable for lower bounds; the overview compares their reach with a new protocol.At three rounds, the earlier protocol solves bPC-Perm_n,10, while the new one solves bPC-Perm_n,12, both at O(n log log n) communication.Source: §2.2 · p. 9
  • IP◦PC combines pointer chasing with an inner product of the resulting vectors, and its lower bound tracks their joint distribution using Rényi entropies.The reduction from IP◦PC to connectivity uses a layered construction.Source: §2.2 · p. 9

3 Preliminaries

The preliminaries establish notation for tuples, permutations, information theory, and the two-party communication model used throughout the paper.

3 Preliminaries

  • For n≥1, [n] denotes {1,…,n}, and x_<i denotes the tuple of entries before position i.The paper also defines analogous prefix and suffix tuple notation.Source: §3 · p. 9
  • An n-permutation is a bijection on [n]; the paper uses cycle decompositions and identifies its matrix representation with σ−1=σ⊤.An n-cycle has one cycle in its decomposition, and there are (n−1)! such permutations.Source: §3 · p. 10
  • The paper defines Rényi entropy and divergence, with orders 1, 2, and ∞ corresponding to Shannon entropy, collision entropy, and min-entropy.It uses H for Shannon entropy and D for KL divergence when context is clear.Source: §3 · p. 10
  • The model is two-party communication with worst-case communication, Alice sending first, and only the last-message receiver required to output unless stated otherwise.The text also defines deterministic, nondeterministic, and r-round randomized complexity notation.Source: §3 · p. 10

4 Nondeterministic Lower Bound for Connectivity

This section proves an optimal nondeterministic lower bound for the balanced bipartite connectivity problem by bounding 1-monochromatic rectangles. Its proof reduces instances recursively and controls the multiplicity created by each reduction.

4 Nondeterministic Lower Bound for Connectivity

  • A one-way deterministic protocol achieves the upper bound by sending Bob a spanning forest of Alice’s edges.Bob updates the forest with his edges and decides connectivity.Source: §4 · p. 10
  • The nondeterministic communication complexity of bConn_N is Θ(N log N), regardless of the number of rounds.The proof obtains the lower bound from the number of 1-inputs and an upper bound on rectangle size.Source: §4 · pp. 11–12
  • The lower bound also implies that any zero-error randomized cut-query algorithm deciding connectivity needs Ω(N) expected queries.The paper states this makes the known cut-query algorithm optimal even when it only decides connectivity.Source: §4 · p. 11
  • There are n!(n−1)! connected inputs, so bounding the largest 1-monochromatic rectangle substantially below that count yields the lower bound.The proof studies rectangles in the permutation formulation of bConn_N.Source: §4 · p. 11

4.1 Proof of Lemma 4.3

  • Shortcutting a three-edge path produces a smaller 1-monochromatic rectangle, reducing the analysis to size n−1.The reduction exposes the remaining randomness in B after conditioning on A(u)=v.Source: §4.1 · pp. 12–13
  • For a fixed shortcut, alternative permutations correspond to vertices whose triples retain the required cyclic order across every a in A.The corresponding 6-cycle implies b−1b′=(u w z); the cyclic-order restriction bounds how many such alternatives are possible.Source: §4.1 · pp. 13–14
  • An edge coloring encodes candidate cycle edges so outgoing and incoming colors uniquely determine the cycle.The construction groups edges by the number of compatible vertices and samples labels; within each color class, the cycle edges form a uniquely recoverable perfect matching.Source: §4.1 · pp. 15–16

5 Lower Bound for Connectivity with Small Error

The section proves error-dependent randomized lower bounds for connectivity by ruling out large weighted, almost 1-monochromatic rectangles. An inductive entropy analysis supports the rectangle bound.

5 Lower Bound for Connectivity with Small Error

  • Ω(N · log(min(1/ε, N))) communication is required for randomized bConnN protocols with error probability ε, regardless of rounds.The theorem applies for even N > 1 and ε ∈ (0, 1/3).Source: §5 · p. 16
  • The proof bounds weighted, almost 1-monochromatic rectangles for bConnN by measuring a product distribution’s probability of disconnected inputs.The section defines this distance as Δ(Q) = Pr_(a,b)∼Q(bConnN(a,b) = 0), with Q ranging over product distributions.Source: §5 · p. 17

5.1 Proof of Lemma 5.2

  • An induction on n analyzes δ-close product distributions by restricting permutations and applying an entropy bound for the reduced instance.Lemma 5.3 supplies an intermediate bound for δ-close product distributions; Lemma 5.2 is proved by induction using restrictions and averaging over u.Source: §5.1 · pp. 20, 22, 23

6 Lower Bound for Connectivity with Constant Error

The section establishes round-dependent randomized lower bounds for connectivity and related graph properties. A layered reduction encodes an inner-product pointer-chasing problem in cycle structure, yielding communication and streaming lower bounds.

6 Lower Bound for Connectivity with Constant Error

  • Ω(N/r · log N) communication is required for r-round randomized bConnN protocols with constant error, for r = o(log N).The reduction extends to connectivity on general N-vertex graphs with the same lower bound.Source: §6 · p. 23

6.2 Lower Bounds for Other Graph Properties

  • Ω(N/r · log N) communication is required to decide bipartiteness, cycle-freeness, Eulerian status, Hamiltonicity, or planarity with constant error for r = o(log N).The proofs use modifications to the connectivity reduction.Source: §6 · p. 23, §6.2 · p. 27

6 Lower Bound for Connectivity with Constant Error

  • Ω(N/p^2 · log N) space is required by p-pass randomized streaming algorithms for connectivity with constant error, for p = o(log N).The proof simulates a p-pass, S-space algorithm with a (2p − 1)-round protocol using O(pS) communication.Source: §6 · p. 23

6.1 Proof of Theorem 6.1

  • The constructed graph has one N-cycle when the composed inner product is 0, and three cycles of lengths N/2, N/4, and N/4 when it is 1.The layers encode permutations and bit-vector-dependent product edges; this cycle structure lets connectivity decide IP◦PC.Source: §6.1 · pp. 24, 26

7 Lower Bound for IP◦PC

The section proves an Ω(n log n) communication lower bound for constant-error r-round IP◦PC protocols when r=o(log n), developing a tighter entropy-loss analysis after first establishing a weaker bound. Its proof augments each message with an analysis-only virtual message that preserves the rectangle property, enabling bounds on conditional event probabilities.

7 Lower Bound for IP◦PC

  • For r=o(log n), every constant-error r-round protocol for IP◦PC_n,r requires Ω(n log n) communication.Theorem 7.1 gives this lower bound for error probability less than 1/2.Source: §7 · p. 28

7.1 A Weaker Lower Bound

  • The weaker analysis proves an Ω(n/r · log n) lower bound for IP◦PC and suffices, by reduction, for the optimal Ω(N log N) connectivity bound at constant rounds.It tracks how much randomness remains in iterated permutation-transformed bit vectors and uses the final inner product to bound the protocol’s ability to predict the output.Source: §7 · p. 28, §7.1 · pp. 29, 33, 35

7.2 Proof of Theorem 7.1

  • The tighter proof aims to limit cumulative entropy loss by charging rounds for revealed information and associating each round with a virtual message to make Shannon and min-entropy nearly equal.The passage contrasts the per-round min-entropy bound with a Shannon-entropy loss whose sum is bounded in expectation by total communication.Source: §7.2 · p. 36
  • The virtual combined message is computable by its owner from its input and partial transcript, is not communicated, and preserves the rectangle property without requiring fixed message lengths.The analysis treats it like an actual message.Source: §7.2 · p. 36
  • O(log n) bounds log(c M_i + 1), limiting the virtual message’s additional length.The proof uses this bound when replacing the original messages with combined messages.Source: §7.2 · p. 36
  • For each index i in [r], the conditional probability of event E_i given E_{i−1} is bounded above by 2^{-n log n}, uniformly over the stated index range.Source: §7.2 · p. 37

AI Methodology

The authors report extensive ChatGPT assistance with exploring, formulating, and improving proof ideas, alongside proofreading and copy-editing; they retain responsibility for the final manuscript.

AI Methodology

  • ChatGPT discovered the edge-coloring argument used to prove Lemma 4.6.The authors identify this as one of the lemmas materially affected by the tool.Source: AI Methodology · p. 39
  • ChatGPT produced an early, weaker error-dependent randomized lower bound, which the authors extended and later improved to an Ω(log(1/ε)) dependency.The preliminary approach had an Ω(log log(1/ε)) dependency and required direct-sum arguments to cover the full range of error probabilities.Source: AI Methodology · p. 39
  • ChatGPT suggested using Hölder’s inequality to optimize a lower-order term in Lemma C.2, relaxing the round requirement but not improving the communication bound.The communication bound for IP◦PCn,r or graph connectivity did not improve.Source: AI Methodology · p. 39
  • ChatGPT also assisted with proofreading and minor copy-editing, while the human authors take full responsibility for the final manuscript.The authors state that responsibility covers correctness and exposition.Source: AI Methodology · p. 39

A Basic Tools from Information Theory

This section introduces information-theoretic quantities used in the paper, including entropy, divergence, and mutual information, and records basic identities and inequalities.

A Basic Tools from Information Theory

  • It defines KL and Rényi divergence between distributions, noting that Rényi divergence at α = 1 is KL divergence.For a uniform reference distribution, the section uses a simplified divergence notation.Source: A Basic Tools from Information Theory · pp. 46–47
  • The section defines Shannon, Rényi, min-, and collision entropy as information measures for random variables.It identifies Rényi entropy at α = 1 as Shannon entropy and at α = 2 as collision entropy.Source: A Basic Tools from Information Theory · p. 46
  • The section defines mutual information through entropy differences and introduces its conditional form.It gives I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X).Source: A Basic Tools from Information Theory · p. 47
  • The listed basic properties include chain rules for Shannon entropy and mutual information, plus conditional mutual-information inequalities under stated independence conditions.The inequalities bound conditional mutual information from above or below after conditioning on an additional variable.Source: A Basic Tools from Information Theory · p. 47

B Round-Efficient Protocols for PC-Perm

This section presents round-efficient deterministic protocols for PC-Perm and bPC-Perm. A coloring-based protocol with a delayed starting vertex supports parallel layer chasing and the stated communication bounds.

B Round-Efficient Protocols for PC-Perm

  • For k ≤ r², PC-Perm has an r-round deterministic protocol with O(nr² log log n) communication.The theorem specifies that the protocol starts with Bob.Source: B Round-Efficient Protocols for PC-Perm · p. 47
  • For k ≤ r² + r, bPC-Perm also has an r-round deterministic protocol with O(nr² log log n) communication.This bit-version protocol likewise starts with Bob.Source: B Round-Efficient Protocols for PC-Perm · p. 47
  • The PC-Perm subroutine solves instances with 2τ−1 layers in τ rounds using O(nτ log log n) communication and delays disclosure of the starting vertex until the last round.It colors layers consistently with pointers, then sends pointers only for vertices matching the starting vertex’s color.Source: B Round-Efficient Protocols for PC-Perm · pp. 47, 49
  • The delayed-start property enables r parallel instances on disjoint layers, gradually chasing through more layers and quadratically improving round complexity.For the bit version, bits are propagated backward in parallel, allowing the protocol to chase through r additional layers.Source: B Round-Efficient Protocols for PC-Perm · pp. 49, 51

C Lower Bound for IP◦PC with More Rounds

Theorem C.1 extends the communication lower bound for IP◦PC to protocols with up to O(n^η) rounds. Its proof replaces a loss in the earlier analysis with a stronger lemma and adjusts the proof parameters.

C Lower Bound for IP◦PC with More Rounds

  • For r = O(n^η), every r-round protocol for IP◦PC_n,r with constant error below 1/2 requires Ω_η(n log n) communication.Theorem C.1 states this for n ≥ 1 and η ∈ (0, 1).Source: C Lower Bound for IP◦PC with More Rounds · p. 51
  • The earlier analysis loses O(rn/log n) in Φ_r, limiting its range to r = o(log n); Lemma C.2 provides the stronger alternative needed for Theorem C.1.The proof of Lemma C.2 uses Hölder’s inequality, and relates Q on permutations to the induced distribution Q(w,z).Source: C Lower Bound for IP◦PC with More Rounds · p. 51
  • The proof tunes ζ = (1 − η)/2 and the thresholds Φ_i, then uses L = ζn/1000 · log n to retain Lemma 7.9 with a modified error term.Item 2’s 2^−n/log n term becomes 2^−nζ/log n.Source: C Lower Bound for IP◦PC with More Rounds · pp. 52–53
Loading 2610.32346v1…