arXiv:2609.05795v1 [cs.DS] 5 Sep 2026
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction Peter Robinson∗
Ming Ming Tan†
Computer & Cyber Sciences Augusta University
Computer & Cyber Sciences Augusta University
Abstract 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 Θ log3 n is optimal for constructing a spanning forest or deciding whether the graph is connected with error at 1 most 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 orspanning tree construction with error at most δ requires messages of length Ω min{n, log2 1δ }1/3 , which implies that algorithms with exponentially small error must send messages of Ω n1/3 bits in the worst case. Our results significantly narrow the current gap between the Nelson-Yu threshold of Θ log3 n 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(n1/7 ), we recover the same bound of Ω(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 = no(1) , our result implies a stronger lower bound of Ωε (nε ) bits, for any constant ε < 13 .
1
Introduction
In the distributed graph sketching model [BMN+ 11], we consider a graph of n nodes that are equipped with unique integer IDs and a referee. The input of each node u consists of the list of its neighbors’ IDs in the graph, and u may send a single message to the referee, who produces the output depending on the received messages. The naive approach for solving any problem in the sketching model is to simply instruct every node to send a message containing all its neighbors’ IDs to the referee, which, however, requires a linear message length and does not scale to large graphs. Thus, the main challenge is designing algorithms that are efficient, in the sense that each node’s message is limited to a polylogarithmic number of bits, i.e., nodes only send a sketch of their neighborhoods to the referee. Deciding whether the graph is connected or constructing a spanning tree are arguably some of the most fundamental graph problems. The work of Ahn, Guha, and McGregor [AGM12] shows that these problems have low-memory implementations in the semi-streaming setting, and it is ∗
Peter Robinson was supported in part by National Science Foundation (NSF) grants CCF-2402836 and CCF2552881. † Ming Ming Tan was supported in part by National Science Foundation (NSF) grant CCF-2348346 CRII.
1
straightforward to adapt their technique to yield distributed graph sketching algorithms that cor- 1 rectly solve these problems with probability at least 1− poly(n) , while sending messages of O log3 n bits per node. The optimality of this threshold remained open for several years, until Nelson and Yu [NY19] showed that Θ log3 n is indeed tight for spanning forest construction; subsequently, Yu [Yu21] proved that the same lower bound holds even for connectivity testing. A natural question to ask is whether access to randomness and allowing a small probability of error are indeed necessary for obtaining efficient graph sketching algorithms with small-length messages. To date, there are no deterministic upper bounds known for connectivity in the distributed graph sketching model that would ensure a worst case message size of o(n), which suggests that we should not hope for a deterministic connectivity algorithm with polylogarithmic message-size. Interestingly, the aforementioned lower bounds of [NY19, Yu21] do not suffice to resolve this question, as their simulation argument introduces an additive error term of roughly 1/nε , for some constant ε > 0, which prevents these techniques from yielding stronger bounds for algorithms with a much smaller probability of error. (We elaborate in more detail on this point in Section 1.3.) Consequently, the 3 best known bounds in the existing literature leave a large gap between the Ω log n barrier and the trivial upper bound of O(n) bits for deterministic connectivity and spanning tree algorithms in the distributed graph sketching model. Obtaining lower bounds on the deterministic complexity of connectivity has been of significant interest to the graph sketching community. For instance, [Ass22] (p. 102) mentions “Prove an nΩ(1) lower bound for deterministic connectivity” under “Harder Open Problems” as a “longstanding open question”, and [SY25] state “Establishing lower bounds in other settings—distributed or streaming, deterministic or randomized—remains an intriguing open question.” Our work takes a significant step towards resolving this fundamental question.
1.1
Preliminaries: Sketching Model and Graph Problems
We consider n nodes each of which is equipped with a unique integer ID of Θ(log n) bits from [n]. Every node knows its neighbors’ IDs as well as n, and may send a single message of B bits to the referee, who does not have any prior information about the graph and who computes the answer based on the received messages. For randomized algorithms, we assume that the nodes and the referee also have shared access to an infinite string of random bits. For spanning tree construction, the referee needs to output the list of edges that form a spanning tree of the graph, whereas for connectivity, the referee simply outputs a bit to indicate whether the graph is connected. Finally, k-edge connectivity requires the referee to answer whether every nontrivial cut of the graph contains at least k edges.
1.2
Our Contributions
We present the first polynomial lower bounds for connectivity testing and spanning tree construction in the tiny error regime, i.e., algorithms that fail with probability at most npoly1log(n) , which includes deterministic algorithms as an important special case. Our main result is the following: Theorem 1. Any randomized algorithm that decides connectivity or computes a spanning tree on an n-node graph in the distributed graph sketching model with error at most δ ≤ log18 n , has a worst n
2
case message length of ! 1 1/3 Ω min n, log2 . δ Instantiating Theorem 1 with δ = 2−n immediately gives the following: Corollary 1. Any deterministic algorithm for connectivity testing or spanning tree construction requires a worst case message length of Ω n1/3 bits in the distributed graph sketching model. The same bound holds for randomized algorithms with exponentially small error. At first glance, it may seem that the bound for the spanning tree problem follows immediately from the one for connectivity. While this is true when considering algorithms for the spanning forest problem, which must work on all (connected or disconnected) graphs, here we explicitly consider spanning tree algorithms that are only guaranteed to work on connected graphs, which requires a separate argument. We point out that the proof of Theorem 1 remains valid for algorithms with a significantly larger error probability than the stated one. However, bound reduces to the known the obtained 3 1 Θ log n threshold of [Yu21, NY19] as soon as δ = Θ log8 n , and does not yield any useful bound n 1 once δ ≥ ω log8 n . n By using a standard “blow-up” construction, where we obtain a larger graph by replacing nodes with cliques, we can extend our connectivity result to k-edge connectivity: Corollary 2. Any randomized graph sketching algorithm that decides k-edge connectivity on an n-node graph with error at most δ ≤ log18 n , has a worst case message length of n
! 1 n 1 1/3 Ω · min , log2 . k k δ For the exponentially small error regime δ ≤ 2−αn , for fixed α > 0, and for deterministic algorithms we obtain the following: • For any k = O n1/7 , the message length is Ω(k). • If k = no(1) , then, for every fixed ε < 31 , the message length is Ωα,ε (nε ) bits.1 Note that Corollary 2 recovers the bound of Ω(k) shown recently by Robinson and Tan [RT26] for deterministic algorithms. In fact, as long as k is subpolynomial, we obtain a bound of Ω(nε ), thus improving over their result.
1.3
Technical Challenges and Our Approach
A major technical challenge in the sketching model emanates from the assumption that every edge is shared between two nodes. In particular, this “vertex partitioning” property of the inputs prevents us from leveraging direct reductions from problems in communication complexity, which is a common lower bound technique in the setting where the edges are partitioned between the players, cf. [WZ17]. The existing lower bounds of [NY19, Yu21] circumvent this obstacle by implementing a “lossy” simulation of the sketching algorithm in the 2-party model of communication complexity. The purpose of the simulation is to construct a solver for variants of the universal relation (UR) 1
Note that the notation Ωγ (. . .) means that the hidden constant may depend on γ.
3
problem [KRW95, KNP+ 17] in the one-way communication model, where Alice gets a subset S of some universe and sends a single message to Bob, whose input consists of some proper subset T ⊂ S. Upon receiving Alice’s message, Bob must output some element in S \ T .2 The UR problem is a classic find-the-needle-in-the-haystack problem, which makes it a natural candidate for proving a lower bound for the amount of communication required to ensure that a node can successfully identify a crucial spanning tree edge among many adjacent edges. To address the technical challenge of the input edges being shared between their neighbors, the simulation of [NY19, Yu21] introduces an error term (in addition to the error of the algorithm), by giving up on simulating the messages sent by a certain subset of nodes. Nevertheless, they show via Pinsker’s inequality [Pin64] that the resulting distribution observed by Bob is statistically close enough to the distribution at the referee in the sketching model. Since the error term of their simulation is roughly n1ε , for some constant ε > 0, this approach does not provide better bounds for algorithms in the tiny error regime, including deterministic algorithms. While our graph construction is similar to the ones in [NY19, Yu21], our overall argument is very different, as we do not attempt to achieve a reduction from a communication complexity problem. In the graph, there are M center nodes, and each center ci has some “noisy” edges to its private neighbors, which are not adjacent to any other center nodes. In addition, there are disjoint sets R0 and R1 of so-called shared neighbors, and ci is connected to a subset Di that lies entirely in either R0 or R1 . That is, for our hard distribution, we first create a partition of the ID space into disjoint sets P1 , . . . , PM , R0 , R1 , all of which have the same size q, and then we sample the corresponding private neighbors Ti ⊆ Pi and shared neighbors Di for each center node ci . To determine whether we choose Di such that Di ⊆ R0 or Di ⊆ R1 , we sample an M -length binary vector X. We can think of (Pi , R0 , R1 ) as being an ordered balanced split (OBS) of the possible ID space of ci ’s neighbors. Note that, after choosing the actual neighbors of ci from these subsets, ci ’s view consists of the IDs in Di ∪ Ti without knowing which ID lies in which set. That is, the message sent to the referee is determined by applying a function to the entire set Di ∪ Ti . We call an OBS safe if for any given set of private neighbors Ti , there is no way of constructing two inputs for ci on which it sends the same message to the referee, where we choose the subset of shared neighbors to lie in R0 in the first input and in R1 in the second input. We then bound the 3-ary Vapnik–Chervonenkis (VC) dimension [KM78, MU02] of the safe OBSs of ci . This enables us to use a theorem of [KM78] (also known as generalized Sauer bound) to obtain an upper bound on the size of any such family of safe OBSs. By using a combinatorial argument on multinomial coefficients, it follows that the probability of sampling a safe OBS for a center node ci is exponentially small in q. Subsequently, assuming that indeed all center node OBSs are unsafe, we derive a lower bound on the probability of actually sampling such “dangerous” triples (Ti , Di0 , Di1 ) for every center ci , which serve as witnesses of the assumed non-safety of the OBSs. We show that the correct spanning tree crucially depends on the values of the sampled binary vector X. However, conditioned on all sampled triples being dangerous, it is impossible for a center node to convey the difference to the referee, since each ci must send the same message for the graph constructed with Xi = 0 as it does for the graph for Xi = 1. Of course, the shared neighbors of ci do have a different view (due to having distinct sets of center neighbors) in these two cases and could, at least in principle, alert the referee of the difference. However, their number is polynomially smaller than the number of center nodes. Thus, for the spanning tree construction problem, we can show that this imbalance prevents the algorithm from computing the correct answer unless the message length is sufficiently large. For the connectivity problem, we use a standard encoder2
Strictly speaking, [Yu21] considers a decision variant of the UR problem. Here we focus our discussion on the search variant to keep the presentation simple.
4
decoder information theoretic argument to obtain the result.
1.4
Additional Related Work
The first work to consider the distributed graph sketching model was by Becker, Matamala, Nisse, Rapaport, Suchan, and Todinca in [BMN+ 11], who proved the hardness of several graph problems for deterministic sketching algorithms, including diameter testing and subgraph detection. They obtain their results by proving that the existence of an efficient protocol for these problems allows one to reconstruct the entire graph, which, of course is impossible without a sufficiently large bound on the message length. They explicitly point out that their approach does not extend to graph connectivity problems. The graph sketching model was further studied by Becker, Montealegre, Rapaport, and Todinca in [BMRT14], who show separations between the power of deterministic, private randomness and public randomness algorithms. More recently, Assadi, Kol, and Oshman [AKO20] showed a lower bound of Ω n1/2−ε bits on the required message length for computing an MIS. In the variant of the distributed sketching model where nodes have access to only private randomness, Holm, King, Thorup, Zamir, and Zwick [HKT+ 19] showed that computing a spanning tree is possible √ with sketches of O( n log n) bits. There is a known equivalence between the distributed graph sketching model and the singleround variant of the broadcast congested clique, as observed by [JLN18, AKO20]. In the latter model, each one of n nodes can broadcast a single message per round that is received by the other nodes at the end of the current round. Pai and Pemmaraju [PP20] showed that Ω logb n rounds are required assuming that nodes can broadcast messages of length b bits. Montealegre and Todinca [MT16] discovered that there is a deterministic r-round connectivity algorithm that sends messages of size O(n1/r log n). In subsequent work, Jurdzinski and Nowicki [JN17] showed how to improve the round complexity to O(log n/ log log n) when considering the standard assumption of O(log n) bits per message.
1.5
Roadmap
In Section 2, we define ordered balanced splits (OBSs) of ID sets and prove a bound on their 3-ary VC dimension. We also prove an upper bound on the probability of obtaining a safe OBS. In Section 3, we define the hard input distribution as a sequence of four sampling steps, which is used to determine the node IDs and the adjacencies for the spanning tree and connectivity graph constructions, and state some of their crucial properties. In Section 4, we continue developing the combinatorial argument of Section 2, by bounding the probability of sampling a so-called “dangerous” triple, which can be viewed as a witness for the non-safety of an OBS. Moreover, we also show how conditioning on the event of sampling only dangerous triples impacts the transcript of the shared neighbors (which we call right-side transcript). Then, we show that the distributional error is sufficiently large for spanning tree construction in Section 5 and for connectivity testing in Section 6. We complete the proof of our main result (Theorem 1) for randomized algorithms via Yao’s lemma in Section 7. Finally, we extend the results to k-edge connectivity in Section 8.
5
2
Ordered Balanced Splits
Throughout this section, we consider two integer parameters q and B. We assume that q is sufficiently large and that B≤
q . 100
(1)
Moreover, we consider U to be a set of size 3q and a function f : 2U → M, where |M| ≤ 2B . Intuitively speaking, we can think of U as a set of possible neighborhood IDs and f as a node’s function that maps a given subset of neighbors to a message from some alphabet M. Definition 1. An ordered balanced split (OBS) of U is a partition of U into subsets (P, R0 , R1 ), where |P | = |R0 | = |R1 | = q. Note that we can think of an OBS of U as a 3-coloring of U with color palette Col = {P, R0 , R1 } (i.e., a map U → Col), if we restrict all colors to occur equally often. The following is an adaptation of Definition 2.1 of [MU02]: Definition 2 (Shattering and 3-ary VC dimension). Let H be a family of ordered balanced splits of U , i.e., H ⊆ {ϕ : U → Col}. We say that H shatters Y if every possible 3-coloring of Y can be obtained by restricting the domain of some ϕ ∈ H to Y . The 3-ary VC dimension of H is the size of the largest set that is shattered by H. The hard lower bound graph instances that we construct in Section 3 will leverage the fact that the referee is unable to compute the correct answer unless nodes distinguish certain input pairs by sending distinct messages. This is captured by the following notion of “safe” behavior: Definition 3. We say that an OBS (P, R0 , R1 ) is safe for f if, for every T ⊆ P , and every pair of nonempty sets D0 ⊆ R0 and D1 ⊆ R1 , it holds that f (T ∪ D0 ) ̸= f (T ∪ D1 ).
(2)
Let Hf be the family of all safe OBS for the given function f . Lemma 1. If Hf shatters a set Y ⊆ U , then, for every pair of distinct subsets A, A′ ⊆ Y of size ⌊|Y |/2⌋, we have f (A) ̸= f (A′ ). Proof. Assume towards a contradiction that the statement is false, which means that there are A, A′ ⊆ Y such that f (A) = f (A′ ). Consider a 3-coloring ϕ of Y such that ′ R0 y ∈ A \ A ; R y ∈ A′ \ A; 1 ϕ(y) = (3) ′; P y ∈ A ∩ A P y ∈ Y \ (A ∪ A′ ). Since Hf shatters Y , there exists an OBS (P, R0 , R1 ) that extends ϕ to a (full) coloring of U . Choose T = A ∩ A′ , D0 = A \ A′ , and D1 = A′ \ A. By assumption, we get f (T ∪ D0 ) = f (A) = f (A′ ) = f (T ∪ D1 ), which shows that (P, R0 , R1 ) is not safe, thus providing a contradiction. 6
(4)
Lemma 2. Recall that the range of function f is of size 2B . It holds that the 3-ary VC dimension of Hf is at most 2B + 3. Proof. Consider any Y ⊆ U of size d that is shattered by Hf . Recall from Lemma 1 that f yields pairwise distinct values for all subsets of Y that have size ⌊d/2⌋, which implies that d ≤ 2B . (5) ⌊d/2⌋ d is the In the remainder of the proof, we obtain an upper bound of d in terms of B. Since ⌊d/2⌋ Pd d largest binomial coefficient in the sum t=0 t = 2d and considering that there are (d + 1) terms in the sum, it follows that d 2d ≥ . ⌊d/2⌋ d+1 Note that the right-hand side is an increasing function in d. Thus, if it was true that d ≥ 2B + 4, we would get 2d 22B+4 ≥ > 2B , d+1 2B + 5
(6)
contradicting (5). We conclude that d ≤ 2B + 3. In the proof of Lemma 3 below, we make use of the following result of [KM78] that we restate for completeness: Theorem 2 ([KM78]). Let F be a family of 3-colorings N -element set and suppose that the P of an 3-ary VC dimension of F is at most d. Then |F | ≤ dt=0 Nt 2N −t . Lemma 3. It holds that |Hf | ≤ 23q (q + 1)(192e)q/32 . Proof. Let c0 = ⌊q/32⌋. Combining Theorem 2 with the upper bound on the dimension derived in Lemma 2 yields c0 2B+3 2B+3 X 3q X 3q X 3q 3q−t 3q 3q |Hf | ≤ 2 ≤2 ≤2 , (7) t t t t=0
t=0
t=0
where we have used the fact that 2B + 3 ≤ c0 , for sufficiently large q in the last inequality. Since the binomial coefficients 3qt are increasing for 0 ≤ t ≤ c0 , it follows that c0 X 3q 3q |Hf | ≤ 23q = 23q (c0 + 1) c0 c0 t=0 3q (since c0 ≤ q) ≤ 23q (q + 1) c0 3eq c0 ≤ 23q (q + 1) . c0 (8) q As long as q ≥ 64, it holds that c0 ≥ 64 , and thus
|Hf | ≤ 23q (q + 1)(192e)c0 ≤ 23q (q + 1)(192e)q/32 , where the last inequality follows from c0 ≤ q/32. 7
Lemma 4. Let (P, R0 , R1 ) be a uniformly at random sampled OBS of U . It holds that (P, R0 , R1 ) is safe with probability at most 2−q . Proof. Since Lemma 3 already provides an upper bound on the size of Hf , it suffices to show that the total number of OBSs of U is sufficiently large. We start by observing that the total number of OBSs corresponds to the multinomial 3q , q, q, q which we will lower-bound next. The Multinomial Theorem (e.g., see Sec. 6.5 in [Ros19]) tells us that X 3q = 33q , (9) a, b, c a+b+c=3q
where the left-hand side is the sum over the multinomial coefficients with three nonnegative parts that add up to 3q. By a straightforward application of the “stars and bars” counting method (see, e.g., Chap. 6 in [Ros19]), the total number of triples (a, b, c) with the property that a + b + c = 3q is 3q + 2 (3q + 1)(3q + 2) = < (3q + 1)2 , (10) 2 2 where the inequality follows from the fact that3q + 2 < 2(3q + 1). 3q 3q Consider two multinomial coefficients a,b,c and a−1,b+1,c , and suppose that two coordinates differ by at least 2; w.l.o.g., a ≥ b + 2. Since 3q a a−1,b+1,c = > 1, (11) 3q b+1 a,b,c 3q it follows that making a multinomial more balanced increases its size. Thus, q,q,q is the largest P 3q term in a+b+c=3q a,b,c , and hence is at least as large as the average. Recalling (9) and (10), this implies 3q 33q ≥ . (12) q, q, q (3q + 1)2 It follows that |Hf | ≤ (q + 1)(3q + 1)2 γ q , 3q
(13)
q,q,q 1/32
where γ = 8(192e) < 12 . In particular, there exists some η > 0 such that γ = 2−1−2η . Since 27 (q + 1)(3q + 1)2 = 2o(q) , for sufficiently large q, it follows that (q + 1)(3q + 1)2 ≤ 2ηq . We conclude that |Hf | ≤ 2−(1+η)q ≤ 2−q . 3q q,q,q
8
3
The Hard Input Graph Distribution
We now describe how we sample the lower bound graph. Note that our graph construction is similar to the constructions pioneered by [Yu21, NY19], and further explored in [Rob23]. For the given parameter q, let M = q2.
(14)
We describe the distribution as four separate sampling steps, as we will need to condition on the information revealed in the individual sub-steps below. • First, we assign the integers in the set W = [(M + 2)q] into randomly sampled subsets as follows: – Step 1A: Choose an ordered partition P1 ∪˙ · · · ∪˙ PM ∪˙ R0 ∪˙ R1 of W uniformly at random, under the restriction that all of these subsets have size q.3 We say that Ui = Pi ∪ R0 ∪ R1 is the support of center ci . – Step 1B: Then, for every i ∈ [M ], independently and uniformly choose Ti ⊆ Pi and nonempty sets Di0 ⊆ R0 and Di1 ⊆ R1 . • Step 2: Sample independently and uniformly a binary vector X = (X1 , . . . , XM ). • Step 3: Sample an independent and uniform index J ∈ [M ]. Equipped with the above random variables, we are ready to describe the graph constructions It will turn out that both graphs are nearly identical except for two specific edges. ST Gconn X,J and GX that we use for connectivity and spanning tree construction, respectively.
ST • Vertices of Gconn X,J and GX : The vertices consist of the center vertices C = {c1 , . . . , cM }, the helper vertices S = {s1 , . . . , sM }, two hub vertices h0 and h1 , and the vertices in the set W defined above.4 The IDs of the vertices in C ∪ S ∪ {h0 , h1 } are fixed in advance and independent of the random variables sampled above, which means that they can be easily identified by their neighbors. The number of described vertices is
N0 = M · q + 2M + 2q + 2 = q 3 + 2q 2 + 2q + 2. In addition, the graph also contains n − N0 many padding vertices. ST • Edges common to Gconn X,J and GX :
{ci , si }
(i ∈ [M ]),
{ci , p}
(i ∈ [M ], p ∈ Ti ),
{h0 , p}
(i ∈ [M ], p ∈ Pi \ Ti ),
{ci , r}
(i ∈ [M ], r ∈ DiXi ),
{h0 , r}
(r ∈ R0 ),
{h1 , r}
(r ∈ R1 ).
Note that every padding vertex is attached as a leaf to the hub h0 . 3 4
Note that ∪˙ denotes the disjoint union operator. By a slight abuse of notation, we use the same variables for the vertex sets as well as for their IDs.
9
(15)
• Special Edge of GST X : We directly connect the two hubs by adding {h0 , h1 }. • Special Edge of Gconn X,J : We use the value of the random index J ∈ [M ] by adding the edge {h0 , sJ }. conn to denote the distribution obtained by sampling the corresponding random variables We use Dn,q ST and constructing the graph Gconn X,J . Similarly, we use Dn,q to denote the distribution for constructing GST X . We conclude this section by showing some crucial properties of these graphs: ST Lemma 5. The following properties hold for a graph GST X sampled from Dn,q : (A) Graph GST X is connected. (B) Consider two distinct binary vectors X, X ′ ∈ {0, 1}M . Then, any spanning tree of GST X contains an edge between a center node and R0 ∪ R1 that does not exist in GST X ′ . Consequently, ST GST X and GX ′ do not have a common spanning tree.
Proof. For (A), recall that the two hub vertices are connected by the edge {h0 , h1 }. Every node in Pi \ Ti is adjacent to h0 , whereas every node in Ra is connected to ha (a ∈ {0, 1}). Moreover, every node in Ti is connected to center ci , as is the helper node si . Finally, every ci has at least one neighbor in R0 ∪ R1 and thus has a path to either of the hubs. We now prove (B). Suppose that Xi ̸= Xi′ , for some i ∈ [M ], and let Ci = {ci , si } ∪ Ti . The only Xi ST edges crossing the cut (Ci , V (GST X ) \ Ci ) in GX are the ones between ci and nodes in Di ⊆ RXi . ST Thus, any given spanning tree of GST X must contain an edge e ∈ (Ci , V (GX ) \ Ci ). Similarly, the X′
ST i cut (Ci , V (GST X ′ ) \ Ci ) in GX ′ , only contains edges connecting ci to some neighbors in Di ⊆ RXi′ . As above, any spanning tree contains an edge e′ ∈ (Ci , V (GST X ′ ) \ Ci ). Recall that RXi ∩ RXi′ = ∅, ST which implies that e ∈ / GX ′ .
Lemma 6. The graph Gconn X,J is connected if and only if XJ = 1. Proof. As in the proof of Lemma 5, observe that every node in Pi \ Ti is adjacent to h0 , whereas every node in Ra is connected to ha (a ∈ {0, 1}). Moreover, every node in Ti is connected to center ci , as is the helper node si . Every ci has at least one neighbor in R0 ∪ R1 and thus has a path to either of the hubs. In other words, every node has a path to one of the two hub nodes, however, in conn contrast to GST X , there is no edge {h0 , h1 } in GX,J . 1 Now suppose that XJ = 1 and recall that the edge {h0 , sJ } ∈ E(Gconn X,J ). Note that DJ ⊆ R1 is nonempty. Thus, there exists a path h0 − sJ − cJ − r − h1 , for some node r ∈ R1 , and thus Gconn X,J is connected. Finally, consider the case XJ = 0. Let Pad be the padding nodes (if any), and define the sets A = {h0 } ∪ R0 ∪
M [
(Pi \ Ti ) ∪ Pad ∪
i=1
B = {h1 } ∪ R1 ∪
[
[
({ci , si } ∪ Ti ),
i:Xi =0
({ci , si } ∪ Ti ).
(16)
i:Xi =1
Observe that A and B are disjoint and partition the set of nodes. According to the construction of Gconn X,J , the cut (A, B) is empty, i.e., the graph is disconnected.
10
4
Unsafe and Dangerous Splits
For each center node ci and each A ⊆ W , let fi (A) be the message sent by the assumed deterministic algorithm when center node ci has the neighborhood A∪{si }. That is, for the given list of neighbors, fi produces a message from an alphabet M of size at most 2B . The alert reader may remark that ci ’s neighbors are chosen from W ∪ {si }; however, we omit si from the domain of fi , because its ID is fixed and independent of the input distribution. Lemma 7. Suppose we sample the partition of the IDs in W according to Step 1A in Section 3, and note that we can think of each triple (Pi , R0 , R1 ) as an OBS of the set of possible neighbors of ci in W . Let All-Unsafe denote the event that, for every center ci , (Pi , R0 , R1 ) is unsafe (see Def. 3). 1 Pr [All-Unsafe] ≥ . Step 1A 2 Proof. Consider a center ci and condition on the support being the set Ui = Pi ∪ R0 ∪ R1 , which has size 3q. According to the hard input distribution, the triple (Pi , R0 , R1 ) is uniform among all possible OBSs of Ui . By Lemma 4, it follows that (Pi , R0 , R1 ) is safe for fi with probability at most 2−q . A union bound over the M = q 2 centers shows that the event that there exists a center for which the sampled OBS is safe happens with probability at most q 2 · 2−q ≤ 21 , for sufficiently large q. Definition 4. Consider an unsafe OBS (Pi , R0 , R1 ) for fi . We say that the triple (Ti , Di0 , Di1 ) is dangerous if fi (Ti ∪ Di0 ) = fi (Ti ∪ Di1 ).
(17)
Intuitively speaking, we can think of a dangerous triple as being a “witness” to the fact that (Pi , R0 , R1 ) is unsafe. We use All-Dangerous to denote the event that every sampled triple is dangerous, and derive a lower bound on its probability next: Lemma 8. Condition on sampling the partition of W according to Step 1A of the input distribution in Section 3 and suppose that the OBS of every center node is unsafe. That is, 3
Pr [ All-Dangerous | All-Unsafe ] ≥ 2−3q .
Step 1B
Proof. Given (Pi , R0 , R1 ), the number of candidate triples of a center node is 2q (2q −1)2 , since there are 2q choices for Ti and 2q − 1 choices each for the (nonempty) subsets Di0 and Di1 . Moreover, each of the 2q (2q − 1)2 ≤ 23q
(18)
candidate triples is equally likely, according to the sampling performed in Step 1B of Section 3. Thus, we choose a dangerous triple for ci with probability at least 2−3q . Recalling that the choices for distinct center nodes are conditionally independent, it follows that we sample dangerous triples 3 for all of the M centers with probability at least 2−3qM = 2−3q . Definition 5 (Right-side Transcript). Let N (r) denote the IDs of the neighbors of a node r and let fr be the (deterministic) message function used by the algorithm at r. We define the right-side transcript to be the sequence Z = (fr (N (r)))r∈R0 ∪R1 , where we fix the order of the nodes in R0 ∪ R1 according to their IDs. 11
(19)
Lemma 9. Condition on events All-Dangerous, All-Unsafe and the sampling in Steps 1A and 1B. Then, for any two distinct binary vectors X, X ′ ∈ {0, 1}M , it holds that every center node sends ST conn the same message for graphs GST X and GX ′ . Moreover, the same statement also holds for GX,J conn and GX ′ ,J . Proof. Under the given conditioning, we have already performed the sampling of Steps 1A and 1B, thus we only need to consider the possible impact of the choices made in Steps 2 and 3. According to the construction of GST X (see Sec. 3), the neighborhood of a center node ci is independent of sampling the index J in Step 3. Moreover, ci is connected to the same helper node si in all graphs ST . Thus, it follows from Definition 4, that c sends the same message no matter sampled from Dn,q i what vector X is sampled in Step 2. To complete the proof, note that all properties used in the proof also hold for the graph construction Gconn X,J . Lemma 10. Condition on the partition and all triples obtained in Steps 1A and 1B of the sampling process in Section 3, and suppose that events All-Dangerous and All-Unsafe occur. (A) The only messages depending on the binary vector X (sampled in Step 2) are part of the right-side transcript Z, which itself is fully determined by X under the given conditioning, i.e., Z = Z(X). (B) There are at most 22qB many choices for Z. Proof. Part (B) follows by observing that there are 2q vertices in R0 ∪ R1 and each of them sends a message of at most B bits. conn We now focus on Part (A). It is immediate from the construction of both, GST X and GX,J , that only the messages sent by the center nodes and the nodes in R0 ∪R1 may depend on X. Furthermore, the conditioning on All-Dangerous guarantees that all center nodes send the same message for every choice of X, as shown in Lemma 9, and hence the only nodes that can distinguish X from X ′ lie in R0 ∪ R1 .
5
The Distributional Error of Spanning Tree Construction
Let Fail denote the event that the referee outputs an incorrect answer. Lemma 11. Condition on the partition and all triples obtained in Steps 1A and 1B, and suppose that events All-Dangerous and All-Unsafe occur. Then, 1 Pr[ Fail | All-Unsafe, All-Dangerous ] ≥ . X 2 Proof. Let S be the set of binary vectors X such that the algorithm correctly outputs a spanning tree for GST X . As a first step, we show that the right-side transcript (see Def. 5) Z(X) has distinct values for all X ∈ S. To this end, recall from Lemma 5(B) that the algorithm must output distinct spanning trees for all distinct X and X ′ . By Lemma 10(A), we know that only the messages in Z depend on X. It follows that Z(X) ̸= Z(X ′ ), as otherwise the referee would output the same spanning tree for X and X ′ . Since Z is injective on S, Lemma 10(B) tells us that |S| ≤ 22qB .
12
Given that X is uniform on {0, 1}M and M = q 2 , it follows that the algorithm succeeds with probability at most 1 22qB−M ≤ 2−49M/50 ≤ , 2
(20)
where we used the assumption that q is sufficiently large. Lemma 12. Consider a deterministic algorithm in which each node sends a B-bit message, where q q is any sufficiently large integer. If n ≥ q 3 + 2q 2 + 2q+ 2 and B ≤ 100 , then the distributional ST is at least Ω 2−3q error of computing a spanning tree on Dn,q
3
.
Proof. We have Pr [Fail ] ≥ Pr [Fail | All-Dangerous, All-Unsafe] · Pr [All-Dangerous | All-Unsafe] · Pr [All-Unsafe ].
ST Dn,q
ST Dn,q
ST Dn,q
ST Dn,q
Conditioned on the partition and triples sampled in Steps 1A and 1B as well as on events All-Dangerous, All-Unsafe, the remaining random choices are the sampling of X and J in Steps 2 and 3, respectively, and GST X is conditionally independent of J. We know from Lemma 5(B) that correct outputs for distinct vectors X and X ′ result in distinct spanning trees, and Lemma 10(A) tells us that only the right-side transcript, i.e., the messages sent by nodes in R0 ∪ R1 can depend on the binary vec1 tor at hand. PrDn,q ST [Fail | All-Dangerous, All-Unsafe] = E[PrX [Fail | All-Dangerous, All-Unsafe]] ≥ 2. Plugging this bound into the right-hand side of the above inequality, we obtain 1 · Pr [All-Dangerous | All-Unsafe] · Pr [All-Unsafe] Step 1A 2 Step 1B 1 1 3 ≥ · 2−3q · 2 2
Pr [Fail ] ≥
ST Dn,q
(by Lem. 7 and 8)
= Ω 2−3q
6
3
.
The Distributional Error of Connectivity Testing
For each j ∈ [M ], we create a deterministic decoder gj by hardwiring J = j and all fixed messages that are not part of the right-side transcript. Thus, gj : range(Z) → {0, 1},
(21)
whereby the output of gj (Z(X)) is the assumed graph sketching algorithm’s decision regarding whether Gconn X,J is connected. Recall from Lemma 6 that the correct answer is XJ . We make use of the following standard random-access inequality, whose proof is similar to Fano’s inequality and the concavity of the binary entropy function. We include a complete proof in Appendix A for completeness. Lemma 13. Let X ∈ {0, 1}M be chosen uniformly at random. Moreover, let Z = Z(X) be a deterministic encoding and let g1 , . . . , gM be deterministic binary decoders. If J is uniform on [M ] and independent of X, then log2 |range(Z)| ≥ M (1 − h2 (ε)), where ε = Pr[gJ (Z) ̸= XJ ] and h2 is the binary entropy function. 13
Lemma 14. Condition on the partition and all triples obtained in Steps 1A and 1B, as well as on events All-Dangerous and All-Unsafe. Then, 1 Pr [Fail | All-Unsafe, All-Dangerous] ≥ . 4
X,J
Proof. Assume towards a contradiction that PrX,J [Fail | All-Unsafe, All-Dangerous] < 14 . By Lemma 13 and the fact that h2 is strictly increasing on [0, 1/2], we have log2 |range(Z)| > M (1 − h2 (1/4)) >
M , 8
(22)
where the last inequality follows because h2 (1/4) < 78 . Recalling that B ≤ q/100 and M = q 2 , and applying Lemma 10(B) yields log2 |range(Z)| ≤ 2qB ≤
M , 50
(23)
contradicting (22). Lemma 15. Consider a deterministic algorithm in which each node sends a B-bit message, where q q is any sufficiently large integer. If n ≥ q 3 + 2q 2 + 2q + 2 and B ≤ 100 , then the distributional conn is at least Ω 2−3q error of deciding connectivity on graphs sampled from Dn,q
3
.
Proof. The proof is similar to Lemma 12 with the key difference being that we apply Lemma 14 instead of Lemma 11. We have Pr [Fail ] ≥ Pr [Fail | All-Dangerous, All-Unsafe] · Pr [All-Dangerous | All-Unsafe] · Pr [All-Unsafe ]. conn conn conn
conn Dn,q
Dn,q
Dn,q
Dn,q
Conditioned on the partition and triples sampled in Steps 1A and 1B as well as on events All-Dangerous, All-Unsafe, the remaining random choices are the sampling of X and J in Steps 2 and 3. Thus, by conn [Fail | All-Dangerous, All-Unsafe] = E[PrX,J [Fail | All-Dangerous, All-Unsafe]] ≥ Lemma 14, PrDn,q 1 4 . Plugging this bound into the right-hand side of the above inequality, we obtain 1 · Pr [All-Dangerous | All-Unsafe] · Pr [All-Unsafe] Step 1A 4 Step 1B 1 1 3 ≥ · 2−3q · 4 2
Pr [Fail ] ≥
conn Dn,q
(by Lem. 7 and 8)
= Ω 2−3q
7
3
.
Completing the Proof of Theorem 1
Theorem 1 (restated). Any randomized algorithm that decides connectivity or computes a spanning tree on an n-node graph in the distributed graph sketching model with error at most δ ≤ log18 n , has n a worst case message length of ! 1 1/3 Ω min n, log2 . δ 14
Proof. Given a randomized algorithm with a worst case message length of a certain number of bits, it is straightforward to modify the algorithm such that every message has length exactly B without changing the asymptotic size of the message alphabet. Thus, we assume that nodes always send B-bit messages throughout the rest of the proof, which means that the size of the message alphabet is at most 2B . We first consider the connectivity problem. Let n′ = min n, log2 1δ , and choose $ % n′ 1/3 q= , (24) 64 which implies ′
3
2−3q ≥ 2−3n /64 .
(25)
For sufficiently large n′ , it follows from (15) that N0 ≤
n′ ≤ n, 16
conn and D ST (see Sec. 3) are supported on n-node which means that the hard distributions Dn,q n,q graphs, possibly by including n − N0 padding vertices. q Now, assume towards a contradiction that B ≤ 100 . Combining the distributional error guaranteed by Lemma 15 with Yao’s minimax lemma [Yao77], reveals that 3 Pr[Fail] ≥ Ω 2−3q ′ (by (25)) ≥ Ω 2−3n /64 ≥ Ω δ 3/64 = ω(δ), (26)
contradicting the assumed error probability being at most δ. It follows that B = Ω(q), which completes the proof for connectivity. The proof of the result for spanning tree construction is analogous: We combine Lemma 12 (instead of Lemma 15) with Yao’s lemma and note that the graph GST X is guaranteed to be connected by Lemma 5.
8
Extension to k-Edge Connectivity
In this section, we prove Corollary 2 via a reduction from the connectivity lower bound obtained in Theorem 1. To prove a lower bound for k-edge connectivity on an n-node graph, we define H to be a graph of n m= (27) k+1 nodes u1 , . . . , um . A straightforward counting argument shows that there is a partition of [n] = V1 ∪ . · · · ∪ Vm such that k + 1 ≤ |Vi | ≤ 2(k + 1)
(i ∈ [m]).
(28)
Definition 6. We define the blow-up Bk (H) on [n] as follows: • We replace each ui with a clique among the vertices in Vi , and call Vi a cluster in Bk (H). • For every edge {ui , uj } ∈ E(H), we add a complete bipartite graph on the vertex sets Vi and Vj . 15
Lemma 16. H is connected if and only if Bk (H) is k-edge connected. Proof. Observe that, if H is disconnected, and consider two vertices ui and uj lying in different connected components. According to Def. 6, we do not add any edges between the corresponding clusters Vi , Vj ⊆ V (Bk (H)), and hence Bk (H) is disconnected as well. Now suppose that H is connected. Consider any nontrivial cut S of Bk (H): First, suppose that S splits a cluster Vi . Let a = |S ∩ Vi |. The clique edges of Vi contribute at least a(|Vi | − a) ≥ |Vi | − 1 ≥ k, where the latter inequality follows from (28). Otherwise, it must be that S is a union of complete clusters H is connected, it S V1 , . . . Vℓ . Since Sℓ ℓ follows that there is at least one edge {uj , uj ′ } in the cut j=1 uj , V (H) \ j=1 uj . According to the construction of Bk (H), the vertices in Vj and Vj ′ form a complete bipartite graph. By (28), we have |Vj ||Vj ′ | ≥ (k + 1)2 ≥ k
(29)
edges across the cut. The simulation of Bk (H) is straightforward since each node knows the fixed partitioning of [n] and can use its local neighborhood information to determine the edges incident to its simulated nodes in Bk (H). The node ui then simply concatenates the simulated messages and sends them to the referee, which, due to (28), may require a message length of up to |Vi |B ≤ 2(k+1)B bits. Apply 1/3 ing Theorem 1 to the simulated connectivity protocol, we get 2(k + 1)B ≥ Ω min m, log2 1δ , and therefore ! 1 1 1/3 B≥Ω · min m, log2 k δ ! 1 n 1 1/3 ≥Ω · min , log2 , (30) k k δ n where the second inequality follows due to m ≥ 2(k+1) (see (28)). Now consider the exponentially small error regime, i.e., δ ≤ 2−αn and thus
log2
1 ≥ αn ≥ αm, δ
which implies 1 min m, log2 ≥ m · min{1, α}. δ Recalling (30), it follows that B=Ω
n1/3 min{1, α}1/3 4/3 k
16
! = Ωα
! n1/3 . k 4/3
(31)
9
AI Disclosure
We used GPT 5.5 as part of our research. In particular, GPT 5.5 suggested to use the theorem of [KM78] for bounding the size of a certain family of the ordered balanced splits with a given 3-ary VC dimension, and also suggested the “blow-up” simulation for extending the results to k-edge connectivity. However, no AI-generated text was included in the paper. All content was written and verified by the authors, including all statements of lemmas, theorems, and their proofs. The authors take full responsibility for all content.
APPENDIX A
Proof of Lemma 13
Lemma 13 (restated). Let X ∈ {0, 1}M be chosen uniformly at random. Moreover, let Z = Z(X) be a deterministic encoding and let g1 , . . . , gM be deterministic binary decoders. If J is uniform on [M ] and independent of X, then log2 |range(Z)| ≥ M (1 − h2 (ε)), where ε = Pr[gJ (Z) ̸= XJ ] and h2 is the binary entropy function. Proof. For each i, define εi = Pr[gi (Z) ̸= Xi ], Ei = Xi ⊕ gi (Z).
(32)
Given Z, the variables Xi and Ei determine one another. Thus, H(Xi | Z) = H(Ei | Z) ≤ H(Ei ) = h2 (εi ). By subadditivity, H(X | Z) ≤
≤
M X i=1 M X
H(Xi | Z)
h2 (εi )
i=1 M
(by concavity of h2 )
≤ M h2
1 X εi M
! = M h2 (ε).
i=1
Since X is uniform, H(X) = M . Therefore I(X : Z) = H(X) − H(X | Z) ≥ M (1 − h2 (ε)). We conclude that I(X : Z) ≤ H(Z) ≤ log2 |range(Z)|.
17
References [AGM12]
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459–467. SIAM, 2012. 1
[AKO20]
Sepehr Assadi, Gillat Kol, and Rotem Oshman. Lower bounds for distributed sketching of maximal matchings and maximal independent sets. In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 79–88, 2020. 5
[Ass22]
Sepehr Assadi. Lower bounds for distributed sketching. In 11th Workshop on Advances in Distributed Graph Algorithms (ADGA) https: // adga-workshop. org/ 2022/ assadi. pdf , 2022. 2
[BMN+ 11] Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Adding a referee to an interconnection network: What can (not) be computed in one round. In 2011 IEEE International Parallel & Distributed Processing Symposium, pages 508–514. IEEE, 2011. 1, 5 [BMRT14] Florent Becker, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. In Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, pages 83–95, 2014. 5 [HKT+ 19] Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, and Uri Zwick. Random k-out subgraph leaves only O(n/k) inter-component edges. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 896–909, 2019. 5 [JLN18]
Tomasz Jurdzinski, Krzysztof Lorys, and Krzysztof Nowicki. Communication complexity in vertex partition whiteboard model. In International Colloquium on Structural Information and Communication Complexity, pages 264–279. Springer, 2018. 5
[JN17]
Tomasz Jurdzinski and Krzysztof Nowicki. Brief announcement: on connectivity in the broadcast congested clique. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 5
[KM78]
Mark G Karpovsky and Vitali D Milman. Coordinate density of sets of vectors. Discrete Mathematics, 24(2):177–184, 1978. 4, 7, 17
[KNP+ 17] Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P Woodruff, and Mobin Yahyazadeh. Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 475–486. Ieee, 2017. 4 [KRW95]
Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5:191–204, 1995. 4
18
[MT16]
Pedro Montealegre and Ioan Todinca. Brief announcement: deterministic graph connectivity in the broadcast congested clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 245–247, 2016. 5
[MU02]
Elchanan Mossel and Christopher Umans. On the complexity of approximating the vc dimension. Journal of Computer and System Sciences, 65(4):660–671, 2002. 4, 6
[NY19]
Jelani Nelson and Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1844–1860, 2019. 2, 3, 4, 9
[Pin64]
Mark S Pinsker. Information and information stability of random variables and processes. Holden-Day, 1964. 4
[PP20]
Shreyas Pai and Sriram V Pemmaraju. Connectivity lower bounds in broadcast congested clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Schloss Dagstuhl-LeibnizZentrum für Informatik, 2020. 5
[Rob23]
Peter Robinson. Distributed sketching lower bounds for k-edge connected spanning subgraphs, BFS trees, and LCL problems. In 37th International Symposium on Distributed Computing (DISC 2023), pages 32–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023. 9
[Ros19]
Kenneth H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill Education, New York, NY, 8th edition, 2019. 8
[RT26]
Peter Robinson and Ming Ming Tan. Deterministic lower bounds for k-edge connectivity in the distributed sketching model. Proceedings of the ACM on Management of Data (PODS 2026), 4(2 (PODS)):1–21, 2026. 3
[SY25]
Pachara Sawettamalya and Huacheng Yu. A (very) nearly optimal sketch for k -edge connectivity certificates. CoRR, abs/2510.16336, 2025. 2
[WZ17]
David P Woodruff and Qin Zhang. When distributed computation is communication expensive. Distributed Computing, 30(5):309–323, 2017. 3
[Yao77]
Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pages 222–227. IEEE Computer Society, 1977. 15
[Yu21]
Huacheng Yu. Tight distributed sketching lower bound for connectivity. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1856–1873, 2021. 2, 3, 4, 9
19