On The Multiparty Communication Complexity of Testing
Triangle-Freeness

arXiv:1705.08438v1 [] 23 May 2017

Orr Fischer∗

Shay Gershtein†

Rotem Oshman‡

May 24, 2017

In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party
communication complexity, focusing on testing triangle-freeness in graphs. We consider the coordinator
model, where we have k players receiving private inputs, and a coordinator who receives no input; the
coordinator can communicate with all the players, but the players cannot communicate with each other. In
this model, we ask: if an input graph is divided between the players, with each player receiving some of
the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is
triangle-free, or far from triangle-free?
For general communication protocols, we show that Õ(k(nd)1/4 + k2 ) bits are sufficient to test trianglefreeness in graphs of size n with average degree d (the degree need not be known in advance). For simul√
taneous protocols, where there is only one communication round, we give a protocol that uses Õ(k n)
√
√
bits when d = O( n) and Õ(k(nd)1/3 ) when d = Ω( n); here, again, the average degree d does not
need to be known in advance. We show that for average degree d = O(1), our simultaneous protocol is
asymptotically optimal up to logarithmic factors. For higher degrees, we are not able to give lower bounds
on testing triangle-freeness, but we give evidence that the problem is hard by showing that finding an edge
that participates in a triangle is hard, even when promised that at least a constant fraction of the edges must
be removed in order to make the graph triangle-free.
∗

Computer Science Department, Tel-Aviv University. Email: orrfischer@mail.tau.ac.il
Computer Science Department, Tel-Aviv University. Email: shayg1@mail.tau.ac.il
‡
Computer Science Department, Tel-Aviv University. Email: roshman@mail.tau.ac.il

†

1

1 Introduction
The field of property testing asks the following question: for a given property P , how hard is it to test whether
an input satisfies P , or is ǫ-far from P , in the sense that an ǫ-fraction of its representation would need to
be changed to obtain an object satisfying P ? Property-testing has received extensive attention, including
graph properties such as connectivity and bipartiteness [22], properties of Boolean functions (monotonicity,
linearity, etc.), properties of distributions, and many others [35, 17, 21]. The usual model in which propertytesting is studied is the query model, in which the tester cannot “see” the entire input, and accesses it by
asking local queries, that is by only viewing a single entry in the object representation at a time. The tester
typically does not have at its disposal the possibility of making a ”non-local” query whose answer depends
on a substantial subset of the object’s representation, which is a primary source of difficulty in property
testing. For example, for graphs represented by their adjacency matrix, the tester might ask whether a given
edge is in the graph, or what is the degree of some vertex. The efficiency of a property tester is measured by
the number of queries it needs to make. One can also distinguish between oblivious testers, which decide
in advance on the set of queries, and adaptive testers, which decide on the next query after observing the
answers to the previous queries. It is known that for many graph properties, one-sided oblivious testers are
no more than quadratically more expensive than adaptive testers [24].
In this paper we study property testing from a different perspective, that of communication complexity.
We focus on property testing for graphs, and we assume that the input graph is divided between several
players, who must communicate in order to determine whether it satisfies the property or is far from satisfying it. Each player can operate on its own part of the input “for free”, without needing to make queries; we
charge only for the number of bits that the players exchange between them. This is on one hand easier than
the query model, because players are not restricted to making local queries, and on the other hand harder,
because the query model is centralized while here we are in a distributed setting. This leads us to questions
such as: does the fact that players are not restricted to local queries make the problem easier, or even trivial? Which useful “building blocks” from the world of property testing can be implemented efficiently by
multi-party protocols? Does interaction between the players help, or can we adopt the “oblivious approach”
represented by simultaneous communication protocols?
Beyond the intrinsic interest of these questions, our work is motivated by two recent lines of research.
First, [10, 19], study property testing in the CONGEST model, and show that many graph property-testing
problems can be solved efficiently in the distributed setting. As pointed out in [19], existing techniques
for proving lower bounds in the CONGEST model seem ill-suited to proving lower bounds for property
testing. It seems that such lower bounds will require some advances on the communication complexity side,
and in this paper we make initial steps in this direction. Second, recent work has shown that many exact
problems are hard in the setting of multi-party communication complexity: Woodruff et al. [38] proved that
for several natural graph properties, such as triangle-freeness, bipartiteness and connectivity, determining
whether a graph satisfies the property essentially requires each player to send its entire input. We therefore
ask whether weakening our requirements by turning to property testing can help.
In this work we focus mostly on the specific graph property of triangle-freeness, an important property
which has received a wealth of attention in the property testing literature. It is known that in dense graphs
(average degree Θ(n)) there is an oblivious tester for triangle-freeness which is asymptotically optimal
in terms of the size of the graph (i.e., adaptivity does not help) [2, 18], and [3] also gives an oblivious
√
tester for graphs with average degree Ω( n). The closest parallel to oblivious testers in the world of
communication complexity is simultaneous communication protocols, where the players each send a single
message to a referee, and the referee then outputs the answer. We devote special attention to the question of

2

the simultaneous communication-complexity of testing triangle-freeness.

1.1 Related Work
Property testing is an important notion in many areas of theoretical computer science; see the surveys [35,
17, 21] for more background.
Triangle-freeness, the problem we consider in this paper, is one of the most extensively studied properties in the world of property testing; many different graph densities and restrictions have been investigated
(e.g., [2, 1, 5, 23]). Of particular relevance to us is triangle-freeness in the general model of property testing, where the average degree of the graph is known
but no other restrictions are imposed. For
√ in advance,
4
2
3 /d 3 }) on testing triangle-freeness, and a lower
nd,
n
this model, [3] showed an upper bound of Õ(min{
√
√
bound of Ω(max{ n/d, min{d, n/d}, min{ d, n2/3 }n−o(1) }), both for graphs with a average degree d
ranging from Ω(1) up to n1−o(1) . For specific ranges of d, [34] and [25] improved these upper and lower
bounds, respectively, by showing an upper bound of O(max{(nd)4/9 , n2/3 /d1/3 } and a lower bound of
Ω(min{(nd)1/3 , n/d), n/d}).
Our simultaneous protocols use ideas, and in one case an entire tester, from [3], but implementing them
in our model presents different challenges and opportunities. (Our unrestricted-round protocol does not bear
much similarity to existing testers.) As for lower bounds, we cannot use the techniques from [3] or other
property-testing lower bounds, because they rely on the fact that the tester only has query access to the
graph. For example, [3] uses the fact that a triangle-freeness tester with one-sided error must find a triangle
before it can announce that the graph is far from triangle-free ([3] also gives a reduction lifting their results
to two-sided error). In the communication complexity setting this is no longer true; there is no obvious
reason why the players need to find a triangle in order to learn that the graph is not triangle-free.
Property testing in other contexts. Recently, the study of property testing has been explored in distributed computing [7, 10, 19]. Among their other results, Censor-Hillel et al. [10] showed that trianglefreeness can be tested in O( ǫ12 ) rounds in the CONGEST model; expanding this, [19] showed that testing
H-freeness for any 4 node graph H can be done in O( ǫ12 ) rounds, and showed that their BFS and DFS
approach fails for K5 and C5 -freeness, respectively; [19] does not give a general lower bound. There
has also been work on property testing in the streaming model [26]. The related problem of computing
the exact or approximate number of triangles has also been studied in many contexts, including distributed
computing [14, 11, 30, 15], sublinear-time algorithms (see [16] and the references therein), and streaming
(e.g., [27]). Specifically, [27] gives a reduction which shows a lower bound on the space complexity of
approximating the number of triangles in the streaming model; we apply their reduction here to show the
hardness of testing triangle-freeness, by reducing from a different variant of the problem used in [27].
Communication complexity. The multi-party number-in-hand model of communication complexity has
received significant attention recently. In [38] it is shown that several graph problems, including exact
triangle-detection, are hard in this model. Many other exact and approximation problems have also been
studied, including [6, 31, 39, 9, 37, 8] and others.
Unfortunately, it seems that canonical lower bounds and techniques in communication complexity cannot be leveraged to obtain property-testing lower bounds; for discussion, see section 4.6.

1.2 Our Contributions
The contributions of this work are as follows:
3

Basic building-blocks. We show that many useful building-blocks from the property testing world can be
implemented efficiently in the multi-player setting, allowing us to use existing property testers in our setting
as well. For some primitives — e.g., sampling a random set of vertices — this is immediate. However, in
some cases it is less obvious, especially when edge duplication is allowed (so that several players can receive
the same edge from the input graph). We show that even with edge duplication the players can efficiently
simulate a random walk, estimate the degree of a node, and implement other building blocks.
Upper
√ bounds on testing triangle-freeness. For unrestricted communication protocols, we show that
Õ(k 4 nd + k2 ) bits are sufficient to test triangle-freeness, where n is the size of the graph, d is its average
degree (which is not known in advance), and k is the number of players. When interaction is not allowed
√
√
(simultaneous
protocols), we give a protocol that uses Õ(k n) bits when d = O( n), and another protocol
√
√
using Õ(k 3 nd) bits for the case d = Ω( n). We also combine these protocols into a single degreeoblivious protocol, which does not need to know the average degree in advance. (This is not as simple as
might sound, since we are working with simultaneous protocols, where we cannot first estimate the degree
and then use the appropriate protocol for it.)
Lower bounds. Our lower bounds are mostly restricted to simultaneous protocols, although we first prove
lower bounds for one-way protocols for two or three players, and then then “lift” the results to simultaneous
protocols for k ≥ 3 players using the symmetrization technique [33].
√
We show that for average degree d = O(1), Ω(k n) bits are required to simultaneously test trianglefreeness, matching our upper bound. For higher degrees, we are not able to give a lower bound on testing
triangle-freeness, but we give evidence that the problem is hard: we show that it is hard to find an edge that
participates in a triangle, even in graphs that are ǫ-far from triangle free (for constant ǫ), and where every
edge participates in a triangle with (small) constant marginal probability.

2 Preliminaries
Unrestricted Communication in the Number-in-Hand Model The default model we consider is this
work is the number-in-hand model. In this model k players receive private inputs X1 , . . . , Xk and communicate with each other in order to determine a joint function of their inputs f (X1 . . . Xk ). This is the most
general model, as the number of rounds of communication is unrestricted. There are three common variants
to this model, according to the mode of communication: the blackboard model, where a message by any
player is seen by everyone; the message-passing model, where every two players have a private communication channel and each message has a specific recipient; the coordinator model, which is the variant we
consider in this paper, and define promptly.
In the coordinator model the players communicate over private channels with the coordinator, but they
cannot communicate directly with each other. The protocol is divided into communication rounds. In each
such round, the coordinator sends a message of arbitrary size to one of the players, who then responds back
with a message. Eventually the coordinator outputs the answer f (X1 . . . Xk ). For convenience, we assume
that the players and the coordinator have access to shared randomness instead of private randomness. Note
that the players will make explicit use of the fact that the randomness is shared for common procedures like
sampling, as the players can agree on which elements to sample simply by agreeing in advance (as part of
the protocol) on how to interpret the public bits, and no interaction is required. (For protocols that use more
than one round, it is possible to get rid of this assumption and use private randomness instead via Newman’s
Theorem [32], which costs at most additional O(k log n) bits. For further details see [29, 32]).
4

The communication complexity of a protocol Π, denoted CC(Π), is the maximum over inputs of the
expected number of bits exchanged between the players and the coordinator in the protocol’s run. For a
problem P , we let CCk,δ (P ) denote the best communication complexity of any protocol that solves P with
worst-case error probability δ on any input.
The coordinator model is roughly equivalent to the widely used message-passing model. More concretely, every protocol in the message-passing model can be simulated with a coordinator, incurring an
overhead factor of at most log k by appending to each message the id of the recipient, to infrom the coordinator whom to forward this message to. The other direction can also be simulated efficiently, as in the
message-passing model we can assign an arbitrary player to be the coordinator and run the protocol as it is.
Although in this paper for convenience we consider the coordinator model, our results consequently apply
for the message-passing model as well, up to a log k factor.
Simultaneous Communication Of particular interest to us in this work are simultaneous protocols, which
are, in a sense, the analog of oblivious property testers. This is the second primary model we investigate
in addition to unrestricted communication. In a simultaneous protocol, there is only one communication
round, where each player, after seeing its input, sends a single message to the coordinator (usually called
the referee in this context). The coordinator then outputs the answer. Any oblivious graph property tester
which uses only edge queries (which test whether a given edge is in the graph or not) can be implemented
by a simultaneous protocol, but the converse is not necessarily true.
Communication complexity of property testing in graphs. we are given a graph G = (V, E) on n
vertices, which is divided between the k players, with each player j receiving some subset Ej ⊆ E of edges.
More concretely, each player, j, receives the characteristic vector of Ej , where each entry corresponds to a
single edge, such that if the bit is 1 then that edge exists in E, and if the bit is 0 it is unknown to the player
whether it exists or not, as this entry might be 1 in the input of a different player. The logical OR of all inputs
results in the characteristic vector of the graph edges, E. Note that there is no guarantee for any vertex for
a single player to have all its adjacent edges in its input, as is the case in models like CONGEST. To make
our results as broad as possible we follow the general model of property testing in graphs (see, e.g., [3]): we
do not assume that the graph is regular or that there is an upper bound on the degree of individual nodes. As
in [38], edges may be duplicated, that is, the sets E1 , . . . , Ek are not necessarily disjoint.
The goal of a property tester for property P is to distinguish the case where G satisfies P from the case
where G is ǫ-far from satisfying P , that is, at least ǫ|E| edges would need to be added or removed from G to
obtain a graph satisfying P . An important parameter in our algorithms is the average degree, d, of the graph
(also referred to as density); for our upper bounds, we do not assume that d is known, but our lower bounds
can assume that it is known to the protocol up to a tight multiplicative factor of (1 ± o(1)). Moreover, as
in [3], we focus on d = Ω(1) and d ≤ n1−ν(n) , where ν(n) = o(1), since for graphs of average degree
d = Θ(n) there is a known solution whose complexity is independent on n in the property-testing query
model and consequently in our model as well. The case of d = o(1), although not principally different, is
ignored for simplicity, as its extreme sparsity makes it of less interest than any degree which is Ω(1).
Information theory. Our lower bounds use information theory to argue that using a small number of
communication bits, the players cannot convey much information about their inputs. For lack of space, we
give here only the essential definitions and properties we need.
Let (X, Y ) ∼ µ be random variables. (In our lower bounds, for clarity, we adopt the convention that
bold-face letters indicate random variables.) To measure the information we learned about X after observ5

ing Y , we examine the difference between the prior distribution of X, denoted µ(X), and the posterior
distribution of X after seeing Y = y, which we denote µ(X|Y = y). We use KL divergence to quantify
this difference:
Definition 1 (KL Divergence). For distributions µ, η : X → [0, 1], the KL divergence between µ and η is
X
D (µ k η) :=
µ(x) log (µ(x)/η(x)) .
x∈X

We require the following property, which follows from the superadditivity of information [13]: if
(X 1 , . . . , X n , Y ) ∼ µ are such that X 1 , . . . , X n P
are independent, and Y can be represented using m
bits (that is, its entropy is at most m), then Ey∼µ(Y ) [ ni=1 D (µ(X i |Y = y) k µ(X i ))] ≤ m. Here and in
the sequel, µ(X i ) denotes the marginal distribution of X i according to µ, and µ(X i |Y = y) is the marginal
distribution of X i given Y = y, and Ey∼µ(Y ) denotes the expectation according to the distribution µ.
Graph definitions and notation. We let deg(v) denote the degree of a vertex v in the input graph, and for
a player j ∈ [k], we denote by dj (v) the degree of v in player j’s input (the subgraph (V, Ej )).
Definition 2. We say that a pair of edges {{u, v} , {v, w}} ⊆ E is a triangle-vee if {u, w} ∈ E, and in this
case we call v the source of the triangle-vee.
Definition 3. We say that an edge e ∈ E is a triangle edge if G contains a triangle T , such that e is an edge
in T .

3 Upper Bounds
All the solutions we present have a one-sided error, that is if a triangle is returned then it exists in G with
probability 1. This holds even when the input is not ǫ-far from being triangle free. Therefore, by solving the
problem of triangle detection, we also solve triangle-freeness, as we never output a triangle in a triangle-free
graph, and do output one with high probability whenever the gap guarantee holds. All algorithms have at
most a small constant bound on the error, δ. We also prove for some cases an improved complexity for
several relaxations such as having the players communicate in the blackboard model, where each message
is seen by all players, or the variant where the players are guaranteed there is no edge-duplication, such
that each edge of the graph appears in exactly one input. Additionally, we assume that k = O(poly(n)), to
simplify the complexity expressions.

3.1 Building Blocks
We start by showing that the essential primitives used in the property testing setting (dense, sparse and
general models combined) of graph problems are efficiently translatable into our communication complexity
model, where the edges of the graph are scattered across k inputs with possible multiplicity and as default the
communication is unrestricted. This illustrates the added power packed in our communication complexity
model, that can solve many problems with at most a logarithmic overhead factor, by simulating the PT
solution, while for some problems, such as the one we will explore here, there is a significantly more
efficient solution.
• Querying a specific edge (check for its existence) - This is one of the main primitives in the dense
model. This can be done in our model in O(k) by having each player send a bit to the coordinator
indicating whether it is in its input, and the coordinator sends the answer bit to all players.
6

• Choosing uniformly a random edge adjacent to a given vertex v - This is the main primitive in the
sparse model. It can be simulated by utilizing the random bits to fix an random order, P , over all the
n−1 potential edges adjacent to v, and have each player send the first edge in his input according to P
to the coordinator, who then sends everyone the first edge according to P of all the edges he received.
This costs O(k log(n)). A random walk, which is a pivotal procedure in sparse property-testing, can
be simulated by taking a random neighbor each step using this primitive. Note that the permutation
was necessary so that edges with higher multiplicity would not be favored, as would happen in a naive
implementation.
• Querying vertex degree - this is an auxiliary query that is sometimes included in the general PT
model. Without duplication this can be done trivially in O(k log(d(v)), by having all players send the
number of edges adjacent to v in their input, and have the coordinator sum them up to get the result.
With duplication, an exact answer costs Ω(kd(v)) as it is at least as hard as solving disjointness, to
ensure no over-counting. However an α-approximation, for any α > 1 can be performed in efficiently
as we promptly prove. We can also reduce the complexity in the no-duplication case by using an approximation, as we also show, and in many cases, such as triangle-detection, a constant approximation
is good enough.
Theorem 3.1. For any given vertex, v, the players can compute an α-approximation, for a constant α > 1 with probability at least (1 − τ ) and communication complexity of O(k log log d(v) +
k log k log log k log τ1 ).
Proof. First each player, Pi , computes locally, di (v), the number of edges adjacent to v in his input,
Ei , and sends Ii , the index of the MSB (the leftmost ’1’ bit in the
representation of di (v)),
P binary
2Ii +1 . This amounts to at most
to the coordinator, who then proceeds to compute the sum d′ =
i∈[k]
P Ii +1
P Ii +1
2
, which is in itself a K-approximation of d(v), where we can only
2
and at least
2
i∈[k]

i∈[k]

′

d
over-count. Hence 2k
≤ d(v) ≤ d′ . The coordinator announces d′ to each player and they proceed to
the next step. The cost so far has been O(k log log d(v)).

In the second phase, the players start a O(log k)-round procedure, where in each round their decrease
√
their guess, d′′ , of d(v), by a multiplicative factor of α, having the starting guess be d′′ = d′ . In
each round they repeat independently an experiment of sampling possible edges (adjacent to v) and
checking whether the sample contains an edge in E. They set a threshold for each round, and if the
number of samples that contained an edge in E exceeds the threshold, they stop and declare the value
of d′′ for that round as the approximated value. If the last guess is reached, the players output it
without running the experiment. Note that the case of d′′ = 1, therefore, is never checked, and we can
assume that d′′ > 2.
In each round, r, we denote d′′ (r) as the value of the guess, d′′ , for that round, and m(r) is the number
of experiments they run. A single experiment is choosing into a set, S(r), every neighbor of v with
probability d′′1(r) , using public randomness, and then each player sends the coordinator a bit indicating
whether S(r) ∩ Ei = ∅. Each round the players assume their guess is correct, and therefore compute
′′
F (r) = (1 − (1 − d′′ (r))d (r) ) as the probability of success in a single experiment, and thus the
expected fraction of successes. The actual probability (as well as the expected fraction of successes)
is E(r) = (1 − (1 − d′′ (r))d(v) ).
7

We wish to prove that, with high probability, if d′′ (r) > αd(v), then the number of successes does
not exceed the threshold, which is F (r)
c , where c is a small constant who value we will determine
later. In that case we have E(r) < F (r) and

F (r)
E(r)

≥

(1−(1−d′′ (r))d

′′ (r)

)

d′′ (r)
(1−(1−d′′ (r)) α )

, which is lower bounded

by, (1 + β1 (α)), where β1 is a constant dependent only on α. The players may assume the lowest
possible value for d′′ , in order for the expression to be dependent only on α, as for d′′ = 2 we get a
small constant bigger than 1, and as d′′ tends to infinity it increases to

1− 1e

1

1−( 1e ) α

. Therefore, by choosing

c to be small enough (less than the square root of the difference) and running a number of experiments
dependent on β1 and τ , a Chernoff bound yields a 1 − τ bound on the probability of exceeding the
τ
threshold. We wish to reduce the error by a Θ(log k) factor, to 2 log
k , so that we may use the union
′′
bound to ensure this deviation doesn’t happen in any round where d (r) > αd(v), and by a Chernoff
argument an increase to m(r) by a factor of O(log log k) suffices.
√ , we exceed the threshold with
On the other hand, we show that the first guess where d′′ (r) < d(v)
α
probability at least (1 − τ /2). Combined with what we proved in the previous case, this proves
that with probability at least (1 − τ ) we stop at a guess which is within the bounds of an alphaapproximation of the d(v), as required.

Now we have d′′ (r) <

d(v)
√
α

that implies E(r) > F (r) and

F (r)
E(r)

≥

′′

(1−(1−d′′ (r))d (r) )
√ ′′
,
(1−(1−d′′ (r)) αd (r) )

which is

upper bounded by constant, β2 (α), dependent only on α. Therefore, m(r) = Θ(log log k) is more
than enough for a constant bound on a constant deviation small enough not to reduce the number of
successes below the threshold.
The total complexity of each round, therefore, is O(k log log k), and summing across all rounds we get
O(k log k log log k). The overall complexity of the algorithm is O(k log log d(v) + k log k log log k).

Lemma 3.2. In the no-duplication variant, for any given vertex, v, the players can compute a αapproximation of d(v), for alpha = O(1), with complexity O(k log log d(v)
k ).
Proof. Each player,Pi , computes locally, di (v), the number of edges adjacent to v in his input, Ei ,
and sends to the coordinator the (log α1 ) most significant bits along with the index of the cutoff,
which takes O(log log di (v)) bits to represent. The coordinator assumes all the missing bits are zeros,
and which makes this an α-approximation of di (v) for each player, when we can only under-count,
and thus the sum of all this approximation, is also an α-approximation. Note that since there is no
duplication, the worst case, by convexity, is when all players have a k1 -fraction of the edges, which
implies the bound stated in the lemma.
Note that this approximation procedure can be applied to any subset of vertex pairs, including estimating the total number of edges in the graph, and not only to the specific set of all possible edges
adjacent to a given vertex. More generally, this solves the problem of estimating the number of distinct
elements in a set.
• Choosing uniformly a random edge - this usually can’t be performed efficiently in the PT model
(unless the standard model is augmented), and is commonly replaced by choosing a random vertex,
and then a random neighbor from the adjacency list. In our model however, we can once again use
8

randomness to fix an order over the edges and each player sends to the coordinator its highest ranked
edge, which is O(log(n)), and across all players this sums up to O(k log n). The coordinator chooses
the highest ranked edge, and posts it to all players.
• Selecting all edges of a subgraph induced by V ′ ⊂ V - this also cannot be performed efficiently
in the PT model, as it requires querying all possible vertex pairs, or going over all relevant adjacency
lists. In our model, on the other hand, it is possible by having each player post all edges (in the
blackboard model the players post in turns so as to not repeat the same edge) of the relevant subgraph
in his input. Let m denote the number of edges in the relevant subgraph, then the complexity is
O(km log n), and it is the same with simultaneous communication (except that only the referee will
know the answer). The complexity is reduced to O(m log n) if there is no edge-duplication, or if the
players communicate using a blackboard. If m is significantly smaller than |V ′ |2 , then our procedure
is more efficient. This is particularly relevant when implementing a BFS. It can be done in O(n log n)
by having all players post all the neighbors of the currently examined vertex.

3.2 Input analysis
Prior to discussing our proposed algorithms, we analyze the properties of the input - a graph ǫ-far from
being triangle free. Our pivotal tool for this analysis is bucketing. We partition V into buckets, such that
for 1 ≤ i ≤ ⌊log3 n + 1⌋ we have Bi = {v ∈ V | 3i−1 ≤ deg(v) < 3i }, whereas B0 is the bucket
of singletons. Note that there are less than log n buckets. Let d− (Bi ) = 3i−1 and d+ (Bi ) = 3i denote
respectively the minimal and maximal bounds on degrees of vertices in Bi . We use d(Bi ) to mean any
degree in that range, when the 3 factor is negligible, and refer to it as the degree of the bucket. We say an
edge is adjacent to a bucket, if it is adjacent to at least one of its vertices. Additionally, we call a set of
triangle-vees disjoint if any two of them are either edge disjoint or originate from a different vertex. Note
that for simplicity we ignore some rounding issues, and avoid using floor or ceiling values.
We are interested in buckets that contain many vertices that participate in a large number of triangles.
Towards that end, we introduce the following definition, and analyze its properties.
Definition 4 (full bucket). We call Bi a full bucket if the edges adjacent to it contain a set of
triangle-vees. Let Bmin denote the bucket with the lowest degree of all the full buckets.

ǫnd
2 log n

disjoint

Observation 3.3. By the pigeonhole principle there is at least one full bucket, as there are at least ǫnd
disjoint triangle-vees.
Lemma 3.4 (size of a full bucket). If Bi is a full bucket then:
ǫnd
2nd
≤ |Bi | ≤ min{n, −
}
+
log n · d (Bi )
d (Bi )
when the upper bound holds regardless of Bi being full.
Proof. The number of disjoint triangle-vees in a full bucket is at least 2 ǫnd
log n . Therefore, the lower bound
pertains to the extreme case when all vertices have the maximal degree d+ (Bi ), that consists entirely of
ǫnd
d+ (Bi )/2 disjoint triangle-vees, thus reaching the sum log
n with as few vertices as possible. The upper
bound follows from the opposite extreme when each vertex contributes as little as possible which is d− (Bi ),
and there are at most d−2nd
(Bi ) such vertices as it would amount to nd edges, the total number of edges in the
graph (the 2 factor follows from counting each edge twice).
9

Definition 5 (full vertex). We call a vertex, v, a full vertex if at least an
to it are a set of disjoint triangle-vees. Additionally, let

ǫ
12 log n -fraction

of the edges adjacent

F (Bi ) = {v ∈ Bi | v is full} ,
be the set of full vertices in Bi . And let
F (V ) = {v ∈ V | v is full} ,
be the set of all full vertices in V .
Full vertices vertices play a vital role in finding a triangles, as they, by definition, participate in many
disjoint triangles. We, therefore, prove several useful lemmas about their incidence, as we are interested in
identifying such vertices, preferably using sampling.
Lemma 3.5. At least an

ǫ
12 log n -fraction

of the vertices in a full bucket, Bi , are full.

Proof. We prove that otherwise there are less than 2 ǫnd
log n triangle-vees adjacent to it, which contradicts it
being full. This holds even if we disregard any double-counting, and assume the bucket has the maximal
, and all its vertex degrees are d+ (Bi ) (both assumptions can not hold simultaneously, but this
size of d−2nd
(Bi )
only strengthens our proof).
The total contribution to the count of triangle-vees coming from non-full vertices is less than:
2nd
ǫ
1
1
· −
· d+ (Bi ) ·
=
ǫnd
2 d (Bi )
12 log n
4 log n
.

+

i)
vees to the count, and if we assume the fraction of full
Each full vertex can contribute at most d (B
2
ǫ
vertices is less than 12 log n , it amounts to less than:

ǫ
2nd
d+ (Bi )
1
· −
·
=
ǫnd
12 log n d (Bi )
2
4 log n

.

overall all vertices combined contribute less than the required

ǫnd
2 log n

to the disjoint triangle-vees count.

Lemmas 3.4 and 3.5 imply the following corollary:
Corollary 3.6. The number of full vertices in a full bucket, Bi , is at least:
|F (Bi )| ≥

ǫ2 · d
·n
12 · log2 n · d+ (Bi )

Next, we single out a set of buckets in proximity to a given bucket, that will play a special role in our
algorithm.
Definition 6 (r-neighbourhood of a bucket). Let r ∈ N such that r ≤ log3 n. We call
Nr (Bi ) = {Bj | j ≥ (i − log3 r)}
the r-neighborhood of bucket Bi , that is the set of all buckets of higher degrees, itself, and the log3 r buckets
right below it in the degree ranking. Additionally, we call
N (Bi ) = Bi−1 ∪ Bi ∪ Bi+1
the neighborhood of bucket Bi .
10

Lemma 3.7. Let Bi be a full bucket. We prove the following lower bound on the ratio of the number of full
vertices in it to the combined size of the buckets in its neighborhood:
ǫ2
|F (Bi )|
≥
|N (Bi )|
312 · log2 n

(1)

on the size of Bj as we have proven in lemma 3.4.
Proof. For any j we have the upper bound d−2nd
(Bj )
Therefore, we have the following upper bound on the sum of bucket sizes:
|N (Bi )| = |Bi−1 | + |Bi | + |Bi+1 |
2nd
2nd
1
2nd
≤3· −
+ −
+ · −
=
d (Bi ) d (Bi ) 3 d (Bj )
26 · nd
26 · nd
=
=
−
3 · d (Bi )
3i
2

·dn
Additionally, we have 12·logǫ2 n·d
+ (B ) as a lower bound on |F (Bi )| (corollary 3.6). Hence, we get the
i
following lower bound on the ratio:

|F (Bi )|
≥
|N (Bi )|

ǫ2 ·dn
12·log2 n·3i
26·nd
3i

=

ǫ2
312 · log2 n

(2)

Lemma 3.8. Let Bi be a full bucket. We prove the following lower bound on the ratio of the number of full
vertices in it to the combined size of the buckets in its r-neighborhood:
ǫ2
|F (Bi )|
P
≥
|Bj |
108 · log2 n · r

(3)

Bj ∈Nr (Bi )

Proof. For any j we have the upper bound d−2nd
(Bj ) on the size of Bj as we have proven in lemma 3.4.
Therefore, we have the following upper bound on the sum of bucket sizes:

X

Bj ∈Nr (Bi )

|Bj | =

X

<

j≥(i−log3 r)

=

9 · ndr
3i

⌊log3 n+1⌋

X

j=(i−log3 r)

⌊log3 n+1⌋

X

|Bj | ≤

j=(i−log3 r)

2nd
3j−1

2nd
6nd · r X 1
6nd · r 3
≤
·
≤
·
j−1
i
m
3
3
3
3i
2
m≥0

2

ǫ ·dn
Additionally, we have 12·log
as a lower bound on |F (Bi )| (corollary 3.6). Hence, we get the fol2
n·3i
lowing lower bound on the ratio:

|F (Bi )|
P
≥
|Bj |

Bj ∈Nr (Bi )

ǫ2 ·dn
12·log2 n·3i
9·ndr
3i

11

=

ǫ2
108 · log2 n · r

(4)

Now we show that we can efficiently sample edges adjacent to a full vertex in order to detect a trianglevee.
Lemma 3.9 (Extended Birthday Paradox). Let v be a vertex of degree d(v) ≥ 2, such that at least αd(v),
for α ≥ 2/d, of the edges adjacent to it are a set of disjoint triangle-vees.
It is enough to sample each edge
q
independently with probability p = c · √ 1 , where c = 4 · ln δ1′ , in order for the sampled set to contain
α·d(v)

a triangle-vee with probability at least (1 − δ′ ).

Proof. The probability of any specific triangle-vee to be sampled is p2 . By the linearity of expectation the
2
expected number of triangle-vees sampled is p2 · αd(v)
= c2 . By a Chernoff bound the probability that less
2
c2

2

2

c2

than one triangle-vee has been sampled is less than e− 4 ·(1− c2 ) ≤ e− 16 = δ′ .

Corollary 3.10. Let v beqa full vertex
q of degree d(v). By sampling independently every edge adjacent to it
log n
6
, we find a triangle-vee with probability at least (1 − δ/6).
with probability p = 4 · ln δ · 12ǫ·d(v)

Proof. We get this trivially by plugging α =

ǫ
12 log n

and δ′ = δ/6 in lemma 3.9.

√
Finally, we prove that there are many triangle-vees adjacent to vertices of degree O( nd), such that we
can focus only on such vertices, and adjust our analysis accordingly.
p
Definition 7. Let Vh denote the subset of V that contains all the vertices with degree at least dh = nd/ǫ.
Let Eh ⊂ E denote all edges with both endpoints in Vh . Finally, let Vl = V \Vh , and let Gl denote the
resulting graph when Eh is removed from G.
Lemma 3.11. Gl is 2ǫ -far from being triangle-free, and there are at least ǫnd/2 disjoint triangle-vees adjacent to vertices in Vl .
√
ǫnd, it follows that Eh < ǫnd
Proof. Because |Vh | ≤ nd
dh =
2 , hence if all edges in Eh are removed, at least
ǫnd
2 additional edges need to be removed from G for it to be triangle-free, as at least ǫnd are required in total
by definition. This also implies that ǫnd
2 of the triangle-vees are adjacent to a vertices in Vl .
Definition 8. Let dl =

ǫd
2 log n .

Lemma 3.12. We have the following bound on degree of vertices in Bmin :
dl ≤ d− (Bmin ) ≤ dh
Proof. The lower bound follows a simple counting argument, as even if all n vertices are in Bmin , if
ǫd
d− (Bmin ) < dl , then the total number of triangle-vees adjacent to Bmin is less than 2 log
n n which contradicts it being full. The upper bound is implied by lemma 3.11 and the pigeonhole principle.
Corollary 3.13. We have:
3

1. |Bmin | ≥=

ǫ2
3·log n

·

√

nd,

5

2. |F (Bmin )| ≥

ǫ2
12·log2 n·3

·

√

nd.

Proof. If plug the upper bound from lemma 3.12 into lemma 3.4 and corollary 3.6 we get the first and second
clause of this corollary respectively.
12

3.3 Unrestricted Communication
The first protocol we present requires interaction between the players, and exploits the following advantage
we have over the query model: suppose that the players have managed to find a set S ⊆ E of edges that
contains a “triangle-vee” — a pair of edges {u, v} , {v, w} ∈ S such that {u, w} ∈ E (but {u, w} is not
necessarily in S). Then even if S is very large, the players can easily conclude that the graph contains a
triangle: each player examines its own input and checks if it has an edge that closes a triangle together with
some vee in S, and in the next round informs the other players. Thus, in our model, finding a triangle boils
down to finding a triangle-vee. (In contrast, in the query model we would need to query {u, w} for every
2-path {u, v} , {v, w} ∈ S, and this could be expensive if S is large.)
Our goal is to find a full vertex. Once that is obtained, we proved in lemma 3.9 we can efficiently sample
a relatively small subset of its edges to find a triangle-vee, thus successfully ending the algorithm.
More
p
concretely, If v is a full vertex, then sampling each of its edges with probability pd(v) = Θ( log n/d(v))
will reveal a triangle-vee with constant probability.
Note that deg(v) may be significantly higher than the average degree d in the graph, so we cannot
necessarily afford to sample each of v’s edges with probability pd(v) ; we need to find a low-degree vertex
which is √
full. Towards that end, we proved in lemma 3.11 we can focus only on vertices of degree at most
dh = O( nd).
With that in mind, we proceed to present our strategy for finding a full vertex. We first describe the core
of the algorithm in a relatively detail-free manner, to emphasize the intuitive narrative leading us throughout
the procedure. This will be followed by a rigorous analysis of the full algorithm.
How can the players find a full vertex? A uniformly random vertex is not always likely to be full —
there might be a small dense subgraph of relatively high-degree nodes which contains all the triangles. In
order to target such dense subgraphs, we use bucketing: we partition the vertices into buckets, with each
bucket Bi containing the vertices with degrees in the range [3i , 3i+1 ). We want to find a full bucket, and
sample its vertices, as we proved that many of them are full. Of course, we cannot know in advance which
bucket is full; we must try all the buckets. Hence, we iterate over the buckets in an increasing order of their
associated vertex degree, up until dh , and for each bucket, assume it is full, and then sampling enough of its
vertices, relying on the lower bound we proved for the number of full vertices in a full bucket, for the sample
to include a full vertex. Then, we sample the edges of each vertex, which for the full vertex will result in
discovering a triangle-vee with high probability. Although, our assumption can be wrong in many cases, we
have proven that there is at least one full bucket, Bi , in that range of degrees, hence the assumption will be
correct at least once, which is enough for our algorithm to succeed with high probability.
It remains to describe, given Bi is a full bucket, how we can sample a random vertex from it, that
is, a random vertex with degree in the range [3i , 3i+1 ). We cannot do that, precisely, but we can come
close. Because the edges are divided between the players, no single player initially knows the degree of any
given vertex. However, by the pigeonhole principle, for each vertex v there is some player that has at least
deg(v)/k of v’s edges, and of course no player has more than deg(v) edges for v.
Let B̃ij := v ∈ V | 3i /k ≤ dj (v) ≤ 3i+1 be the set of vertices that player j can “reasonably suspect”
S
belong to bucket i, where dj denotes the degree of vertex v in the input of player j, and let B̃i := j B̃j . By
the argument above, Bi ⊆ B̃i . Also, B̃i ⊆ Nk (Bi ), since the total degree of any vertex selected cannot be
smaller than 3i /k. Therefore, sampling uniformly from B̃i is a good proxy for sampling from Bi , although
we may also hit adjacent buckets. Nevertheless, we have proven that a full bucket must be large, and hence
constitutes at least roughly a k1 -fraction of B̃i and Nk (Bi ). Hence a uniformly random sample will yield a
vertex from Bi with probability at least roughly 1/k, and Θ̃(k) samples yield a vertex from Bi with high

13

probability.
Lemma 3.14. Let Bi be a full bucket. It suffices to sample uniformly with replacement m = ln ( 6δ ) ·
108·log2 n·r
ǫ2

vertices from Nr (Bi ), in order for the sampled set to contain a vertex from F (Bi ) with probability
at least (1 − 6δ ).
2

ǫ
Proof. The probability of sampling a vertex from F (Bi ) is p = 108·log
according to Lemma 3.8. There2
n·r
fore, the probability of not having a vertex from F (Bi ) after m samples is bounded by (1 − p)m ≤ e−mp =
δ/6.

To implement the sampling procedure we need two components: first, we need to be able to sample
uniformly from B̃i . The difficulty here is that each vertex v ∈ B̃i can be known to a different number of
players — possibly only one player j has v ∈ B̃ij , possibly all players do. If we try a naive approach, such as
having each player j post a random sample from B̃ij , then our sample will be biased in favor of vertices that
belong to B̃ij for many players j. Our solution is to impose a random order on the nodes in B̃i by publicly
sampling a permutation π on V (this is done by interpreting the random bits as a permutation on V ), and we
then choose the smallest node in B̃i with respect to π. This yields a uniformly random sample, unbiased by
the number of players that know of a given node. We call this procedure SampleUniformFromB̃i .
Algorithm 1 SampleUniformFromB̃i
1: π ← random permutation on V
j
2: Each player j sends the coordinator the first vertex in B̃i with respect to π
3: The coordinator outputs the first vertex with respect to π of all the vertices it received
Our sample is too large to treat every sampled vertex as if it is a full vertex from Bi . Sampling edges
for each vertex is too costly and wasteful, since it is possible that only a k1 -fraction of the sampled vertices
are even in Bi . The second component, therefore, verifies that a sampled √
node indeed belongs to Bi . We
cannot do that exactly, but we can come sufficiently close. We compute a 3-approximation of the degree
of the sampled node, as explained in Theorem 3.1, and discard vertices whose approximate degree does not
match N (Bi ). This substantially reduces the size of the sampled set without discarding any vertex from Bi .
We call this procedure ApproxDegree(v).
The protocol for player j is sketched in Algorithm 2. Here N = Θ̃(k) is the number of samples from
B̃i required to produce a sample from Bi with good probability. Following the procedure described in
Algorithm 2, the coordinator sends all the edges he received to all the players, and the players then check
their own inputs for an edge that closes a triangle with some triangle-vee sent by the coordinator. With high
probability, a triangle-vee is discovered, and the protocol completes in the next round.
We move on to a more rigorous analysis of the sampling parameters and the complexity. First we
compute the number of vertices we need to uniformly sample from N (Bi ) to find a full vertex, so that we
can bound the number of vertices we examine while retaining a high probability of preserving a full vertex.
2

n
Lemma 3.15. Let Bi be a full bucket. It suffices to sample uniformly with replacement m = ln ( 6δ )· 312·log
ǫ2
vertices from N (Bi ), in order for the sampled set to contain a vertex in F (Bi ) with probability at least
(1 − 6δ ).
2

n
according to Lemma 3.7. ThereProof. The probability of sampling a vertex from F (Bi ) is p = 312·log
δ·ǫ2
fore, the probability of not having a vertex from F (Bi ) after m samples is bounded by (1 − p)m ≤ e−mp =
δ/6.

14

Algorithm 2 Code for player j
For each i = 0, . . . , log n:
ℓ←0
Repeat until ℓ ≥ N :
v ← SampleUniformFromB̃i
¯ ← ApproxDegree(v)
d(v)
√
√
¯ ≤ 3d+ (Bi ):
If d− (Bi )/ 3 ≤ d(v)
ℓ←ℓ+1
Jointly generate a public random set S ⊆ V , where each u ∈ S with iid probability pd(v)
¯
Send Ej ∩ ({v} × S) to the coordinator
2

n·k
. we use q as
We now present the procedure GetFullCandidates(Bi ). Let q = ln ( 6δ ) · 108·log
ǫ2
a bound on the total number of samples, and we also bound the number of samples that pass the degree
approximation criteria. Both bounds are needed to ensure worst case complexity.

Algorithm 3 GetFullCandidates(Bi)
1: count ← 0
2: C ← ∅
2
n
3: Do until count = q or |C| = ln ( 6δ ) · 312·log
ǫ2
4:
count ← count + 1
5:
v ← SampleUniformFrom
B̃i
√
6:
compute d′ (v), a 3-approximation of d(v), such that the error probability is at most
d− (B )

7:
if √3 i
8: output C

√
≤ d′ (v) ≤ 3d+ (Bi ) then add v to C

δ
3q

Lemma 3.16. The complexity of GetFullCandidates(Bi ) is O(k2 ·log4 n log log n), and in the no-duplication
variant it is O(k2 · log3 n).
Proof. Each vertex the players send to the coordinator costs O(log n), therefore the overall complexity
of choosing uniformly a vertex from U (Bi ) is O(k log n). According to Theorem 3.1, the complexity of
a constant approximation of d(v) for vertex v, when the error bound is Θ( 1q ), is O(k · log k · log log k ·
(log log n + log k)) = O(k · log2 n · log log n), and in the no-duplication variant it is O(k log log nk ). The
number of iterations is at most q = O(k log2 n), hence the total complexity is O(k 2 · log4 n log log n), and
in the no-duplication variant it is O(k2 · log3 n).
√
Lemma 3.17. If Bi is a full, then C contains a vertex from F (Bi ) along with a correct 3-approximation
of its degree with probability at least 1 − 2δ
3 .
Proof. First, note that a union bound implies that all O(q) vertex approximations were correct with probability at least (1 − 3δ ). Due to the symmetric process of sampling in algorithm 1, the vertices are chosen
uniformly from B̃i . Lemma 3.14, when substituting r = k, implies that q uniform samples is enough to
sample a vertex from F (Bi ) with probability at least (1 − 6δ ). And since B̃i ⊆ Nk (Bi ), sampling from
B̃i can only improve our probability of finding a full vertex. Additionally, lemma 3.15 assures us that
2
n
uniform samples from N (Bi ) is enough to encounter a full vertex with probability at least
ln ( 6δ ) · 312·log
ǫ2
δ
(1− 6 ). Note that if all degree approximations are in the guaranteed range, then all vertices sampled from Bi
15

are added to C, and all other vertices that are added are in N (Bi ). Since our sampling process is symmetric
and therefore uniform, vertices sampled into C have at least the same probability of containing a full vertex,
2
n
samples suffice. By a
as in the case of sampling uniformly from all of N (Bi ), and thus ln ( 6δ ) · 312·log
ǫ2
union bound argument, the probability of all approximations being correct, and both sampling processes
sufficing for finding a full vertex, is at least (1 − 3δ ) − 2 · 6δ ) = (1 − 23 δ). Finally, if both sampling processes
would encounter a full vertex, we find it no matter which stopping condition made us halt, therefore it is
also the probability of containing a full vertex in the output.
By this point we know how to efficiently obtain, given Bi is a full bucket, a small sample of vertices that
is likely to contain one full vertex from Bi . All that is left is to iterate over the sampled set, sampling edges
adjacent to each vertex, such that for the full vertex the sample will contain a triangle-vee.
Algorithm 4 SampleEdges(v)
1: S ← sample every possible edge adjacent to v with probability p = 4 ·

r
q
n
ln 6δ · 12dlog
′ (v)

2: each player j sends the coordinator S ∩ Ej if this set is of size at most (1 +
3: the coordinator outputs S ∩ E

ǫ·

18
d′ (v)·p

3

ln δ6 ) ·

√ ′
3d (v)p

Algorithm 5 FindTrinagleVee(Bi)
1: C ← GetFullCandidates(Bi )
2: for each v ∈ C let S ← SampleEdges(v) and then the coordinator posts all the edges to all the players.
3

Lemma 3.18. The communication complexity of FindTrinagleVee(Bi ) is O(k · log 2 n ·
log4 n log log n)

p

d(Bi ) + k2 ·

Proof. The cost of GetFullCandidates is O(k2 · log4 n log log n). Each edge required O(log n) bits to
identify, and since there is a limit on the size of the set the players can send, the overall complexity is
p
3
O(k · log 2 n · d(Bi ) + k2 · log4 n log log n).

Lemma 3.19. If Bi is a full bucket then the players find a triangle with probability at least 1 − δ using
procedure FindTrinagleVee(Bi ).

Proof. According to lemma 3.17, C contains a full vertex with probability at least (1 − 23 δ), and the approximation procedure of its degree gave a correct output. And according to corollary 3.10, if v is a full vertex,
then sampling each of its edges with probability p suffices to sample a triangle vee, with probability at least
(1 − 6δ ). Moreover, the expected size of the sampled set is d(v) · p, and by a Chernoff bound the probability
of sampling more the cutoff size specified in step 2 of the sampling algorithm is at most δ/6. Overall, with
probability at least (1 − δ), one of the vertices sampled will be full, with the players knowing approximately
its degree, and hence sampling enough of its edges so that they find a triangle-vee, and do not need to send
a set above the cutoff size. When that happens, one of the players will respond to the coordinator with the
third edge completing the triangle-vee into a triangle, and the algorithm will end successfully.
All that is left is to find a full bucket. This is achieved by iterating all the relevant buckets. Note the
common theme which is that the players do not know how successful each sampling process was up until
the algorithm terminates. They do not know which bucket is full, which of the sampled vertices are full,
16

or which of its adjacent edges belong to triangles. Since they examine all bucket, all sampled nodes (after
preliminary filtering), and send all sampled edges, that knowledge is redundant, as when they encounter a
full bucket and a full vertex they will be treated as such as a working assumption. Our analysis culminates
in algorithm FindTrinagle(G), which nests inside it all the procedure we presented so far.
Algorithm 6 FindTrinagle(G)
1: Run FindTrinagleVee(Bi) for every bucket starting the first bucket such that d− (Bi ) ≥ dl and until the last bucket

where d+ (Bi ) ≤ dh

Theorem 3.20. If the input graph is ǫ-far from √
being triangle free, then the players can find√a triangle with
4
nd log5/2 n + k2 log5 n log log n) = Õ(k 4 nd + k2 ). The
probability at least (1 − δ)
and
complexity
O(k
p
complexity is in fact Õ(k d(Bmin ) + k2 ) w.p. at least 1 − δ.

Proof. According to lemma 3.12, one of the iterations of FindTriangleVee is performed on Bmin , which is a
full bucket. According to lemma 3.19, the players find a triangle in that iteration with probability (1−δ). The
maximal complexity of an iteration grows as d(Bi ) grows. The number
of iterations is O(log n). Therefore,
p
with probability at least (1 − δ), the overall complexity is O(k d(Bmin ) log5/2 n + k2 log5 n log log n).
However, if an error occurs,
players will go over all buckets √
in the given range, thus in the worst
√ then the
5/2
5
2
case the complexity is O(k dh log n + k log n log log n) = Õ(k 4 nd + k2 ).
Corollary 3.21.
There is a one-sided error protocol for
testing triangle-freeness with communication
com√
√
p
4
4
5/2
4
2
2
plexity O(k nd log n+k log n log log n) = Õ(k nd+k ). The complexity is in fact Õ(k d(Bmin )+
k2 ) w.p. at least 1 − δ.
Corollary 3.22. The variant where the players are not given d has the same complexity.
Proof. The players can compute 2-approximations of dh and dl , denoted by d′h and d′l , respectively, and then
use d′l /2 and 2d′h as the boundaries for the iteration condition. The added complexity is negligible, and the
error can be reduced to an arbitrarily small constant. The rest of the algorithm remains the same, and does
not rely on any knowledge of d.
Theorem 3.23. In the blackboard model, if the input graph is ǫ-far from
being triangle free, then the players
√
4
can√find a triangle with probability at least (1p
− δ) and complexity O( nd log5/2 n + k2 log5 n log log n) =
4
2
Õ( nd + k ). The complexity is in fact Õ( d(Bmin ) + k2 ) w.p. at least 1 − δ. The same protocol also
solves testing of triangle-freeness.
Proof. In the blackboard model, posting the edges of the sub-procedure SampleEdges(v) can be implemented more efficiently, having each player post the edges on the blackboard in turns, ensuring no edge is
posted twice. This saves a k factor in the communication cost with regards to the coordinator model.

3.4 Simultaneous Communication
In the simultaneous model, the players cannot interact with each other — they send only one message to the
referee, and the referee then outputs the answer. This rules out our previous approach, as exposing a trianglevee does not help us if the players cannot then check their inputs for an edge that completes the triangle.
Indeed, the simultaneous model is closer to the query model in spirit. Accordingly, we include trianglefreeness testers of [3], but show that we can implement them more efficiently in our model. Moreover, we
achieve roughly the same complexity without knowing the average degree in advance.
17

√
√
We present separate algorithms for the case of d = Ω( n) and d = O( n), referred to as high and low
√
degrees, respectively. when d = Θ( n), both algorithms are essentially identical. We conclude with an
algorithm that works for the more general case where d is unknown to the players.
3.4.1

high degrees

√
Forpgraphs with average degree Ω( n), the tester from [3] samples a uniformly random set S ⊆ V of
Θ( 3 n2 /d) vertices, queries all edges in S 2 , and checks if the subgraph exposed contains a triangle. It is
shown in [3] that if the graph is ǫ-far from triangle-free, then the subgraph induced by S will contain Θ(1)
triangles in expectation, and the variance is small enough to ensure small error.
We can implement this tester easily, and in our model it is less expensive: instead of querying all pairs
in S 2 , the players simply send all the edges from S 2 in their input, paying only for edges that exist and not
for edges that do not exist in the graph. The set S is large enoughthat the number of edges in the subgraph
does not deviate significantly from its expected value, Θ (nd)1/3 .
We present an algorithm of complexity O(k(nd)1/3 ). We later show, in the lower-bounds section, that
√
for average degree Θ( n) this is tight for 3 players.
Algorithm 7 FindTringleSimHigh(G)
q

2

1: S ← a uniformly random set of vertices of size c 3 nǫd , for a sufficiently large c
2: players send all edges in the subgraph induced by the vertices in S. If the number of edges to be sent by a player
2

4
exceeds l = |S|
n2 δ nd, send any l edges.
3: The Referee checks whether the union on edges it received contains a triangle, and outputs accordingly.

√
Theorem 3.24. The problem of triangle detection, when d = Ω( n) is known to the players, can be solved
with communication cost of O(k(nd)1/3 log n) and a constant error.
Proof. Let δ denote the required bound on the error, and let VS denote the subgraph of G induced by S. In [3]
it was shown that for a sufficiently large c, the probability of VS not containing a triangle is arbitrarily small,
and for our purposes taken as δ/2. Additionally, the probability of each edge appearing in VS is |S|·|S−1|
n·(n−1) ,
thus by the linearity of expectation the expected number of edges in VS is

|S|·|S−1|
n·(n−1) nd

<

l

2
δ

. Finally, by a

Markov argument we get that the probability of the number of edges in VS exceeding l is at most δ/2. When
that happens, even if every player has all the edges, none of them exceeds l, and overall, by a union bound
argument, we get that the referee receives all edges in VS and they contain a triangle, with probability at
1
least (1 − δ). The complexity is at most O(kl log n) = O(k(nd) 3 log n).
Corollary 3.25. The problem of triangle-detection in the no-duplication variant can be solved in the simultaneous model with a constant error, δ, such that the complexity is O((nd)1/3 log n) with probability at least
(1 − δ), and the worst case complexity is O(k(nd)1/3 log n).
Proof. The players would use algorithm 7 as in the general case, thus the worst case complexity is the same.
But as we proved, with probability at least 1 − δ the total number of edges in the subgraph is O((nd)1/3 ),
and since there is no duplication, that is also the total number of edges sent.

18

3.4.2

low degrees
√
For density d = o( n), the approach above no longer works, as the variance is too large. To illustrate this,
consider a graph with d vertices of degree Θ(n), which are the sources of Θ(nd) triangle-vees, such that all
triangles have at least one such node. If we were to sample vertices uniformly at random, we need to sample
Θ(n/d) vertices in order for the subgraph to contain a triangle. However, whereas in the query model we
would need to make Θ(n2 /d2 ) queries to learn the entire subgraph induced by the set we sampled, in our
model we proceed as follows (using ideas from [3], which require adaptivity there, and deploying them in
a different way): let S be the set of Θ(n/d) uniformly-random vertices. We sample another smaller set, R,
√
of Θ( n) vertices, and we send all edges in R × (S ∪ R). If indeed there is a small set of high-degree
vertices participating in most of the triangles, then with good probability we will have one of them in S, and
by the birthday paradox, one of its triangles will have its other two vertices in R. On the other hand, if the
triangles are spread out “evenly”, then the subgraph R × R will probably contain one. The expected size of
√
√
R × (S ∪ R) is O( n), and we show that w.h.p. the total communication is Õ(k n).
√
Note that both our solutions work for d = Θ( n), and for this density they are essentially the same:
√
both sets, S and R, are of size Θ(n/d) = Θ(d) = Θ (nd)1/3 , so for d = Θ( n) the second protocol is
not very different from the first. We can also show that if edge duplication is not allowed, a factor of k is
saved in the communication complexity with high probability.
Algorithm 8 FindTriangleSimLow(G)
S ← sample each vertex with probability p1 = min{ dc , 1}
2: R ← sample each vertex with probability p2 = √cn
3: Players send all to the referee edges with one endpoint in R and the second endpoint R ∪ S. If the
√
number of such edges in the input of a player exceeds q = 2c2 ( n + d) · 2δ , that player sends any q
edges.
4: The Referee checks whether the union of the edges it received contains a triangle, and outputs accordingly.
1:

Where c is a constant to be determined later.
√
Theorem 3.26. The problem of triangle detection in the simultaneous model when d = O( n) is known to
√
the players, can be solved with communication cost of O(k n log n) and with constant error.
Proof. We show that algorithm 8 is such a solution. Let δ denote the required constant bound on the error,
let VR denote the graph induced by R, and let VRS denote the graph on R ∪ S that includes all edges with
at least one endpoint in R. Since each player sends at most q edges, the complexity of the algorithm is
√
O(qk log n) = O(k n log n).
2
The probability of a given edge appearing in VR is p22 = cn , therefore by linearity of expectation, the
2
expected number of edges in VR is at most nd · cn = c2 d. The probability of any edge having one endpoint
in S and the other in R is at most 2p1 p2 , therefore by linearity of expectation, the expected number of such
√
edges is at most 2ndp1 p2 ≤ 2c2 n. Overall, we get that the expected number of edges in VRS , which are
the only edges the players may send, is at most ( q2 ) , and by a Markov argument we get that with probability
δ

at least (1 − 2δ ) the number of edges in VS does not exceed q, thus all players can send all the edges they
have in VRS .
We show that with probability at least (1 − 2δ ) the edges in VRS contain a triangle, which via a union
bound proves that the referee will receive a triangle with probability at least (1 − δ). Recall Gl , the graph
19

defined in definition 7 to be the subgraph on all edges adjacent to at least one vertex of degree at most dh .
For the purpose of analysis, ignore all triangle that are not in Gl . According to lemma 3.11, Gl is 2ǫ -far
from being triangle-free, and thus it contains a family of 6ǫ nd edge-disjoint triangles. Fix such a family, T .
Note that in any triangle in Gl , at most one vertex in can be of degree higher than dh . Further restricting the
number of triangles counted, we only count triangles where at least two vertices of degree at most dh were
sampled into R, which implies that if the third vertex is of degree higher than dh it must be sampled into S.
Let X be a random variable equal to the number of triangles in VRS with the aforementioned restrictions.
The probability of such a triangle to be sampled is at least p1 p22 , therefore the
ǫ
ǫ
E[X] ≥ ndp1 p22 = c2
6
6

(5)

.
We now bound the variance of X. For each t ∈ T , let Xt be an indicator of t being sampled (with our
restrictions). Let dT (v) ≤ d(v) denote the degree of vertex v when only edges of T are left in the graph.
Observe that if two triangles have no vertices in common, then they are selected independently. Additionally,
note that two triangles in T can have at most one vertex in common, as all triangles are edge disjoint. The
probability of two triangles with a joint vertex being both sampled can be split into two cases, one where
the joint vertex is in S, and the second case is when it is sampled into R.
The probability when the joint vertex is sampled into S, is p1 p42 . The number of triangles that can have

P
dT (v) ≤ 2nd, by convexity we get
vertex v in common and sampled into S is at most dT (v)/2
. Since
2
v∈V

dT (v)/2 
2

P

v∈V

≤

2d
P

i=1

n/2
2

≤ 2d ·

n2
8

.

As for the case when the common vertex, v, is sampled into R (note that it means that dT (v) < dh ),
the probability of both triangles being sampled is p21 p32 . The number of vertices of degree dh is at most
P dT (v)/2
2nd
≤
2
dh , and once again by convexity we get that the number of such triangles is smaller than
v∈Vh

P

v∈Vh

dh /2
2

≤

2nd
dh

·

d2h
8 .

Therefore, the variance of X is, for d > c, bounded by:
X dT (v)/2
X dT (v)/2
4
V ar[X] ≤
p1 p2 +
p21 p32
2
2
v∈V

v∈V ∩R

n2
2nd d2h 2 3
≤ 2d · p1 p42 +
· p1 p2
8
dh
8
2
n c c 4 2ndǫ nd c 2 c 3
(√ ) + √ ·
( ) (√ )
≤ 2d ·
8 d n
n
dn 8ǫ d
5
5
5
c
c
c
=
+ √ ≤
4
2
4 d

and similarly for d ≤ c (which implies that p1 = 1, S = V and d = T heta(1)) we get that the variance
5
is also bounded by c2 .
We conclude by employing a Chebyshev bound:
Pr(X < 1) ≤ Pr(|X − E[X]| ≥

V ar 2 (X)
8ǫc4
4
δ
1
E[X]) ≤
≤
=
<
2
((1/2) E[X])2
18c5
9c
2
20

Where the last inequality follows by taking c =
probability at least (1 − δ/2).

8
9δ .

Therefore, VRS contains at least one triangle with

√
Corollary 3.27. The complexity of the no-duplication variant is O( n log n) with probability at least (1 −
√
δ), and the worst case complexity is O(k n log n).

Proof. The players would use algorithm 8 as in the general case, thus the worst case complexity is the
same. But as we proved, with probability at least 1 − δ the total number of edges in the subgraph between an
√
endpoint of R and S is O( n), and the total number of edges in the subgraph of R is at most O(d) and since
√
there is no duplication, that is also the total number of edges sent, which implies complexity O( n).
3.4.3

Degree Oblivious Algorithm

We start with a high-level overview of how we combine the protocols above and modify them so that they
can be used without advance knowledge of the degree. The challenge here is that no single player can get a
good estimate of the degree from their input, and since the protocol is simultaneous, the players must decide
what to do without consulting each other. The natural approach is to use log n exponentially-increasing
“guesses” for the density, covering the range [1, n], and try them all; however, if we do this we will incur
a high cost for guesses that imply examining a larger sample than needed. We, therefore, take a more
fine-grained approach.
Our first observation is that some players can make a reasonable estimate of the global density, although
they do not know that they can. Let d¯j denote the average degree in player j’s input Ej , and let us say that
player j is relevant if d¯j ≥ (ǫ/(4k))d, and irrelevant otherwise. If we eliminate all the irrelevant players
and their inputs, the graph still remains (ǫ/2)-far from triangle-free, so we can afford to ignore the irrelevant
players in our analysis — except for making sure that their messages are not too large.
Since players cannot know if they are relevant, all players assume that they are. Based on the degree
d¯j that player j observes, it knows that if it is relevant, then the average degree in the graph is in the range
 log n
Dj = [d¯j , Θ(k d¯j )]. We fix in advance an exponential scale 2i i=0 of guesses for the density, and execute
in parallel log n instances of triangle-freeness protocols, one for each degree 2i . However, each player j only
participates in the O(log k) instances corresponding to density guesses that fall in Dj , and sends nothing for
the other instances. The protocols are the two algorithms we have presented for a known average degree,
with some modification. For relevant players, we know that the true density falls in their range Dj , so they
will participate in the “correct” instance. For irrelevant players, we do not care, and their message size is
also not an issue: their density estimate is too low, and the communication complexity of each instance
increases with the density it corresponds to.
If we are not careful, we may still incur a blow-up in communication, as relevant players may use
guesses lower than the true density by a factor of k, which increases the size of the sample beyond what is
necessary. However, by carefully assigning each player j a communication budget depending on d¯j , we
can eliminate the blow-up, and match the degree-aware protocol up to polylogarithmic factors.
We now move on to a detailed analysis of the algorithm, which relies on an integration of modified
versions of the algorithms we presented in theqnon-oblivious sections. First, we alter the algorithm for highdegrees, such that instead of sampling |S| =

3

n2
ǫd

2/3

= Θ( nd1/3 ) vertices without replacement, we sample each

−1/3 ). Additionally, we remove
vertex independently (with replacement) with probability Θ( |S|
n ) = Θ(nd
the cap on the number of edges allowed to be sent from both algorithms (high and low degrees). Let Alghigh
denote the modified algorithm for high degrees, and Alglow - for low degrees. We provides figures for both.

21

Algorithm 9 AlgHigh (G)
1: S ← a uniformly random set of vertices of size c

q
3

n2
ǫd ,

for a sufficiently large c

2: players send all edges in the subgraph induced by the vertices in S.
3: The Referee checks whether the union on edges it received contains a triangle, and outputs accordingly.

Algorithm 10 AlgLow (G)
S ← sample each vertex with probability p1 = min{ dc , 1}
2: R ← sample each vertex with probability p2 = √cn
3: Players send all to the referee edges with one endpoint in R and the second endpoint R ∪ S.
4: The Referee checks whether the union of the edges it received contains a triangle, and outputs accordingly.
1:

Lemma 3.28. Alghigh detects a triangle with a small constant error.
Proof. By choosing sufficiently large constants, we ensure that the expected number of triangles is not lower
than the expected value before the alteration. The bound on the deviation, follows the same analysis as in
the proof of the original algorithm, and analogous to the correctness proof of Alglow , as when bounding the
variance in the number of edge-disjoint triangles, only triangles with one common vertex are dependent. In
terms of complexity, we once again use a Markov argument to claim that the total number of edges in the
sampled subgraph does not exceed the expectation by a large constant factor with high probability.
Alglow obviously also remains correct, as removing the cap could only increase the chances of detecting
a triangle. Moreover, both algorithms have the same complexity as before with probability at least (1 − δ),
as implied by their respective complexity analysis in the previous section. We will reinstall modified caps
further into our analysis.
The main sub-procedure the players utilize in both algorithms is choosing jointly, via public randomness,
a subset S ⊆ V , such that each vertex is chosen independently with probability p, and then posting all edges
in their inputs with both endpoints in S. We show that the number of edges each player has in S does not
significantly exceed the expectation, given his average degree.
Lemma 3.29. Let S ⊆ V denote a set where each vertex was sampled with probability p. The number of
edges player j has in the subgraph VS induced by S is O(nd¯j · p2 · logn log(k log n)), such that this holds
for all players with high probability Θ(1).
Proof. Recall the bucketing partition we used in the section of input analysis. For a given player j, we
partition V into O(log n) buckets as we did before, only this time according to dj (v) and not d(v). Since
each vertex is chosen independently, we may utilize the Chernoff bound to claim that when sampling with
probability p, the degree of each sampled vertex is reduced from dj (v) to O(p · dj (v) log(nk)) = O(p ·
1
). Therefore, by the union bound this holds true for all
dj (v) log n), with probability of error at most O( nk
n vertices in the inputs of all k players, with a small constant error.
Next, we also claim that the number of vertices chosen from each bucket, B, is at most O(p·|B| log(k log n)),
1
with probability of error at most O( k log
n ), once again due to a Chernoff argument. A union bound implies
this holds true for all O(log n) buckets for all k players with a small constant error. Overall, if the number
of vertices chosen from each bucket deviates by at most a O(log(k log n)) factor from the expectation, and
each vertex degree is reduced to a size that deviates by at most an O(log n) factor from its expectation, we
22

get that for all k players the number of edges they have in the sampled subgraph deviates from its expected
value (given d¯j ), by at most a O(log n log(k log n)) factor.
For a given guess of the average degree d′ , let p(d′ ) denote the probability with which the players need
to sample each vertex. Recall that all relevant players will include p(d) in their range of guesses (the 2 factor
difference is asymptotically insignificant), hence the union of all the sampled edges includes a triangles with
high probability. We note that for our purposes, an increase of the degree guess, d′ , by a factor of 2 decreases
the sampling probability, p(d′ ), also by at most a factor of 2, therefore there is no dangerous super-constant
blowup in the sampling probability that would otherwise incur an asymptotic overhead on the complexity.
Observe that the guess for the average degree varies inversely as the corresponding sampling probability
and thus expected sample size.
√
√
We first discuss the case where for player j, d¯j = Ω( n), which implies d = Ω( n). The player
performs simultaneously O(log k) algorithms
each with a different guess, d′ , of the average degree. For
√
3
′
′
high degrees this means p(d ) = Θ( nd ).
We now prove that the complexity bound on the message for each player can remain roughly the same,
with the error remaining constant. More concretely,
each player limits separately each of the O(log k) simul√
3
¯
j
taneous algorithms by sending at most O( nd log n log (k log
√ n)) edges. This implies that the complexity
bound of this player over all its simultaneous instances is O( 3 nd log2 n log k log (k log n)).
√
3
Lemma 3.30. A complexity bound of sending at most O( nd¯j log n log (k log n)) edges for each instance
of Alghigh suffices for the instance, pertaining to the correct guess, to send all the edges in its corresponding
subgraph.
Proof. Let r(j) = dd¯j denote the ratio between the correct average degree and the player’s observed average
degree. The expected number of edges player j has in the sampled subgraph for a correct guess is
1/3
p
√
(nd¯j )
3
nd¯j
¯j ) ≤ O( 3 nd)
n
)
=
Θ(
)
≤
O(
Θ(
d
(nd)2/3
r(j)2/3

where we used the fact
that r(j) = Ω(1). Therefore, player j can limit the edge budget of each algorithm
√
3
with a bound of O( nd¯j log n log (k log n)) following lemma 3.29, with all k players not exceeding the
bound with high probability.
This lemma along with the fact that we’ve shown that the sample pertaining to the correct guess contains
a triangle with high probability implies correctness with constant error.
√
Now we deal with the case d̄i ≤ n. As in the previous case the player performs O(log k) algorithms
covering the relevant degree range. And as before all relevant players include the correct guess in their
range of guesses, implying that the union of messages of all players contain a triangle with high probability
following the same analysis as in the non-oblivious case.
√
The player splits the relevant range
of degrees into two cases. For every degree guess, d′ , where n ≤
√
ǫ n
¯j
¯j
empty) the player simulates the algorithm for high
d′ ≤ 4k
ǫ d (Note that when d ≤ 4k this range is √
3
degrees as we just described (with an edge limit of O( nd¯j log n log (k log n)) for each algorithm).
√
√
If indeed d ≥ n then correctness and complexity analysis for that case is the same as when d¯j ≥ n.
√
Whereas for every guess, d′ , where d¯j ≤ d′ ≤ n, the player simulates the AlgLow using d′ instead
of d. More concretely, the player samples into S each vertex with probability p = min{ dc′ , 1}, and the
of sampling into R each vertex with probability Θ( √1n ) as in the original algorithm remains the same (the
players can use the same R across all simultaneous instances).
23

√
We use a cap of O( n log n log (k log n)) edges for each instance of AlgLow and, as the we promptly
prove, it suffices for the correct instance.
√
Lemma 3.31. A complexity bound of sending at most O( n log n log (k log n)) edges for each instance of
√
AlgLow , suffices, for the case where d ≤ n, for the protocol pertaining to the correct guess to send all the
edges in its corresponding subgraph.
√
¯j
Proof. The expected number of edges player j has in R is Θ( nnd ) = Θ(d¯j ) = O( n). It is not surprising
that the expected number did not increase, as the sample size does not depend on the average degree, and
we have already assumed, in our previous analysis, the worst case of each edge in R appearing in all inputs.
√
For the correct guess, d′ = d ≤ n, the expected number of edges player j has connecting S and
√
¯j
R is Θ( dn√d n ) = O( n). Therefore, the expected number of edges player j needs to send overall for the
√
√
correct guess is O( n), and indeed, for all guesses where d′ ≤ n, player j can limit the edge budget
√
of each algorithms with a bound of O( n log n log (k log n)) following lemma 3.29, with all k players not
exceeding the bound with high probability.
Since the complexity (and the edge cap) is higher for the simulations of AlgLow than for the simulations
of AlgHigh , the simulations of AlgHigh do not affect the overall computation of the complexity asymptotically.
√
To conclude, when d ≤ n, the message cost of each player, j, is
√
1
O(max{ n, (nd¯j )1/3 } log2 n log k log (k log n)) = O((nd) 3 log2 n log k log (k log n))
1

thus the overall complexity of the protocol for all players is O(k(nd) 3 log2 n log k log (k log n)).
√
√
√
Whereas when d ≤ n then d¯j ≤ n, and the complexity of player j is O( n log2 n logk ), thus for k
√
players we get O(k n log2 n logk ).
We summarize our complete procedure for all cases in F indT riangleSimOblivious(G). The correctness follows the fact that all relevant players participate in the instance pertaining to the correct guess, and
what we have proved about the edge cap not limiting that instance.
Theorem 3.32. The problem of d-oblivious triangle detection in the simultaneous model can be solved with
√
√
1
communication cost of O(k n log2 n log k log (k log n)) for d = O( n), and in O(k(nd) 3 log2 n log k log (k log n))
√
for d = Ω( n), by a single algorithm, with constant error in both cases.
Algorithm 11 FindTriangleSimOblivious(G)
1:
2:
3:
4:
5:
6:

Each player j ∈ [k] runs simultaneously O(log k) protocols - for each degree guess d′ - covering its
¯j
relevant degree range, Dj = [d¯j , 4k
ǫ d ]:
√
for each guess d′ ≥ n:
run AlgHigh and send up to O((nd)( 1/3) log n log (k log n)) edges
√
for each guess d′ < n:
√
run AlgLow and send up to O( n log n log (k log n)) edges
The Referee checks whether the union of edges it received contains a triangle, and outputs accordingly.

24

4 Lower Bounds
Our main result in this section is the following:
√
ǫ be the task of finding a triangle edge in graphs of size n and
Theorem 4.1. For any d = O( n), let Tn,d
average degree d which are ǫ-far from triangle-free. Then for sufficiently small constant error probability
δ < 1/100 we have:


1/6
ǫ
.
(1) For k > 3 players: CCsim
k,δ (Tn,d ) = Ω k · (nd)



ǫ ) = Ω (nd)1/3 .
(2) For 3 players: CCsim
(T
3,δ
n,d

√
To show both results, we first prove them for average degree d = Θ( n), and then easily obtain the
√
result for lower degrees by embedding a dense subgraph of degree Θ( n) in a larger graph with lower
overall average degree.
√
To prove (1), we begin by proving that for graphs of average degree Θ( n), three players require
ǫ √ in the one-way communication model, where Alice and Bob
Ω(n1/4 ) bits of communication to solve Tn,
n
send messages to Charlie, and then Charlie outputs the answer. In fact, our lower bound is more general,
and allows Alice and Bob to communicate back-and-forth for as many rounds as they like, with Charlie
observing the transcript. We then “lift” the result to k > 3 players communicating simultaneously, using
symmetrization [33].
To prove (2), we show directly that in the simultaneous communication model, three players require
√
ǫ in graphs of average degree Θ(√n).
Ω( n) bits to solve Tn,d
Our lower bounds actually bound the distributional hardness of the problems: we show an input distribution µ on which any protocol that has a small probability of error on inputs drawn from µ requires high
communication. This is stronger than worst-case hardness, which would only assert that any protocol that
has small error probability on all inputs requires high communication.

4.1 Information Theory: Definitions and Basic Properties
We start with an overview of our information theory toolkit, which is our primary technical apparatus for
directly proving lower bound (as opposed to reductions, which we also use to derive subsequent results).
Definition 9. The mutual information between two random variables is I(X; Y ) = H(X) − H(X|Y ) =
Ey∼Y [D (µ(X|Y = y) k µ(X))].
Lemma 4.2 (Super-additivity of information). If X 1 , . . . , X n are independent, then
I(X 1 , . . . , X n ; Y ) ≥

n
X

I(X i ; Y ).

i=1

Lemma 4.3. Let p, q ∈ (0, 1), and let D (q k p) denote the KL divergence between Bernoulli(q) and
Bernoulli(p). Then for any p < 1/2 we have D (q k p) ≥ q − 2p.
Proof. Since the divergence is non-negative, it suffices to show that for p < 1/2, for any q ≥ 2 · p we have
D (q k p) ≥ q − 2p.
For convenience, let us write q = p + x, where −p ≤ x ≤ 1 − p. Our goal is to show that when x ≥ p,
we have D (p + x k p) ≥ x − p.
25

Consider the difference
g(x, p) = D (p + x k p) − (x − p)
1−p−x
p+x
+ (1 − p − x) log
− (x − p).
= (p + x) log
p
1−p
At x = p we have g(x, p) ≥ 0 (since divergence is always non-negative); we will show that the derivative
w.r.t. x is non-negative for x ≥ p, and hence g(x, p) ≥ 0 for any x ≥ p.
Taking the derivative with respect to x, we obtain
∂
p+x
p
1
1−p−x
1−p
1
g(x, p) = log
+ (p + x) ·
·
− log
− (1 − p − x) ·
·
−1
∂x
p
p + x p ln 2
1−p
1 − p − x (1 − p) ln 2




x
x
= log 1 +
− log 1 −
−1
p
1−p
The derivative is increasing in x, and since we consider only x ≥ p, it is sufficient to show that it is nonnegative at x = p:


p
∂
= log (1 + 1) − log 1 −
g(x, p)
−1
∂x
1−p
x=p
p
− 1 ≥ 0.
≥1+
1−p
In the last step we used the fact that log(1 − z) ≤ −z for any z ∈ (0, 1); in our case, since p < 1/2, we
have p/(1 − p) < 1.

√
4.2 Random Graph of Degree Θ( n)
In this section, we derive our main results, lower bounds for one-way and simultaneous communication, all
√
using a single distribution, µ, for graphs of average degree Θ( n), whose edges are shared among 3 players.
In the subsequent sections we move on to showcase methods to generalize these results for k players and
other average degrees.
4.2.1

The input distribution and its properties
√
Our lower bounds for degree Θ( n) use the following input distribution, µ: we construct a tripartite graph
√
G = (U ∪ V1 ∪ V2 , E), where each edge appears iid with probability γ/ n for some constant γ.
This distribution has very high probability that the input is ǫ-far from being triangle-free, but it does not
guarantee it with probability 1. Still, if we can show some task (finding a triangle, or finding a triangle-edge)
is hard on µ, then it is also hard on the distribution µ′ obtained from µ by conditioning on the input being
ǫ-far from triangle-free.
Observation 4.4. Let Π be a protocol for some task T , with error probability at most δ on some distribution
µ supported on a class X of inputs. Then for any Y ⊆ X , the error probability of Π on µ|Y is at most
δ/ Prµ [Y].

26

Proof. We can write:
δ ≥ Pr [Π errs on X]

= Pr [Π errs on X | X ∈ Y] Pr [X ∈ Y] + Pr [Π errs on X | X 6∈ Y] Pr [X 6∈ Y]

≥ Pr [Π errs on X | X ∈ Y] Pr [X ∈ Y] .
The claim follows.
In our case we have:

Lemma 4.5. When γ is sufficiently small, a graph sampled from µ is O(1)-far from triangle-free with
probability at least 1/2.
Proof. Let T be the random variable of the set of triangles in the graph, and let I be the set of pairs of
triangles that share an edge. let
 
n
γ
γ3
E[|T |] =
( √ )3 ≥ n3/2
3
n
12
 
1
n
γ
E[|I|] = 3
(n − 3)( √ )5 ≤ E[|T |]
2
3
n
Where the last inequality follows from choosing a sufficiently small γ. It follows that E[|T | − |I|] ≥ 21 |T |.
Let D denote the maximal size of a set disjoint triangles in the graph. Note that D ≥ |T | − |I|, since given
the set T of triangles, we can for each pair in I choose one of the intersecting triangles, and remove the other
from T . this process halts after |I| steps and we are left with a set disjoint triangles of size at least |T | − |I|.
3
Therefore E[D] ≥ γ24 · n3/2 . Denote X = n2/3 − D, and let |E| be the size of the set of edges in the graph.
Trivially |E| ≥ D, therefore
2 /((1−γ)2 )

P r(X ≤ 0) ≤ Pr(n2/3 − |E| ≤ 0) =≤ Pr(n2/3 ≤ |E|) ≤ e−m

where the next to last inequality follows from chernoff bound on the number of edges in the graph. Since
X gets negative values with exponentially small probability, and is only polynomial in value, it holds that
E[X|X > 0] ≤ (1 + o(1)) E[X]. Therefore
E[D]
γ3
For convenience denote c1 = 2n
2/3 = 48 . It follows that
Pr(D ≤ c1 n3/2 ) = Pr(X ≥ (1 − c)n3/2 ) =

Pr(X ≥ (1 − c1 )n3/2 |X > 0) Pr(X > 0) + Pr(X ≥ (1 − c1 ) · n3/2 |X ≤ 0) Pr(X ≤ 0) ≤
2
2
E[X|X > 0]
E[X]
Pr(X ≥ (1 − c1 ) · n3/2 |X > 0) + e−m /((1−γ) ) ≤
≤ (1 + o(1))
+ o(1) =
(1 − c1 )n2/3
(1 − c1 )n2/3
(1 + o(1))

1 − 2c1
n2/3 − E[D]
+ o(1) = (1 + o(1))
+ o(1)
2/3
1 − c1
(1 − c1 )n

1
(1 − c1 )n2/3 is a constant smaller than 1, meaning (1 + o(1)) 1−2c
1−c1 + o(1) is smaller than some constant
c2 < 1. Therefore with constant probability there are at least c1 disjoint triangles.

27

Therefore, any lower bound we prove for µ translates to asymptotically the same bound on a distribution
that is ǫ-free from triangle-free, namely, µ conditioned on being ǫ-free from triangle-freeness.
Let X e be an indicator variable for the presence of edge e in the input graph. For a transcript t of a
communication protocol Π, let
√
∆t (e) := Pr [X e = 1 | Π = t] − 2γ/ n.
Lemma 4.6. We have:
E

t∼π

"

X
e

#

∆t (e) ≤ |Π|.

√
Proof. For each edge e, the prior probability that e ∈ E is γ/ n, so by Lemma 4.3, for any transcript t,
∆t (e) ≤ D (π(X e |Π = t) k π(X e )) ,
By super-additivity of information,
|Π| ≥ I(Π; E) ≥
= E

"

≥ E

"

t∼π

t∼π

X

I(Π; X e )

e

#

X

D (π(X e |Π = t) k π(X e ))

X

∆t (e).

e

e

#

Covered and reported edges. Our lower bounds show that it is hard for the players to find an edge that
belongs to a triangle. Intuitively, in order to output such an edge, the players need to identify some edge
{v1 , v2 } that (a) is in the input, and (b) closes a triangle together with some third vertex u; that is, for some
u, the edges {u, v1 } and {u, v2 } are also in the input.
We formalize the notion of “finding” an edge satisfying some property using the posterior probability of
the edge satisfying this property given the transcript.
Definition 10 (Reported edges). Given a transcript t, let
Rep(t) = {e ∈ E | Pr [e ∈ E | Π = t] ≥ 9/10}
be the set of edges whose posterior probabilities of being in the input increase to at least 9/10 when transcript t is sent. We call the edges in Rep(t) reported.
Definition 11 (Covered edges). Given a transcript t, let
C (t) = {e ∈ V1 × V2 | Pr [∃u ∈ U : (u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | Πt] ≥ 9/10}
be the set of edges in V1 × V2 whose posterior probability of being covered by a vee rises to at least 9/10
upon observing transcript t. We say that edges in C (t) are covered by Alice and Bob. Let Cov (e) be an
indicator for the event that e ∈ C (Π).
28

4.2.2

One-Way Communication

Consider a protocol Π between three players — Alice, Bob and Charlie — where Alice and Bob communicate back-and-forth for as many rounds as they want, with Charlie observing their transcript, and finally
Charlie outputs an edge from his side of the graph. We claim that the total amount of communication
exchanged by Alice and Bob must be Ω(n1/4 ).
The underlying intuition for our proof is that by the end of the protocol Charlie needs to be informed
√
by Alice and bob of at least Ω( n) vertex pairs in V1 × V2 being covered with high certainty by a vee in
their input. This is due to the fact, that only a Θ( √1n )-fraction of these pairs is expected to have an edge
connecting them. We prove that the number of pairs Alice and Bob can on average inform Charlie of being
covered is at most quadratically larger than their bit-budget, which implies that Ω(n1/4 ) bits are required for
such communication, that succeeds with high probability.
This result is somewhat surprising as the a priori probability of any edge in Charlie’s input belonging to
a triangle is already constant, and elevating only one of these probabilities to 1 − delta suffices for solving
the problem. This observation is equally valid for simultaneous communication.
Theorem 4.7. For any constant γ ∈ (0, 1), if Π solves the triangle-edge-finding problem under µ with error
δ ≤ 1/100, then |Π| = Ω(n1/4 ).
Proof. Suppose for the sake of contradiction that there is a protocol Π with communication αn1/4 , where α
satisfies:
(100α2 + 10α) < (9/20)/γ,
and error δ ≤ 1/100.
√
Say that transcript t of Π is good if |C (t) | ≥ n/(2γ).
Lemma 4.8. Pr [Π is good] ≥ 1 − 20δ.
Proof. If t is not a good transcript, then because C (t) is independent of E 3 ,
√
√
E [|E 3 ∩ C (t) |] ≤ (γ/ n) · ( n/(2γ)) = 1/10.
By Markov, Pr [E 3 ∩ C (t) 6= ∅] ≤ 1/2. Whenever E 3 ∩ C (t) = ∅, Charlie must output an edge that is
either not in his input (E 3 ), or not covered by t; in the first case this is an error, and in the second case, the
probability of an error is at least 1/10, independent of E 3 (it depends only on E 1 , E 2 , which are independent
of E 3 , even given Π = t). Therefore, conditioned on E 3 ∩ C (t) = ∅, the error probability is at least 1/10;
and overall, for any t that is not good,
Pr [error | Π = t] ≥ Pr [E 3 ∩ C (t) = ∅] · (1/10) ≥ 1/20.
Since the total probability of error is bounded by δ, we obtain
X
δ ≥ Pr [error] =
Pr [error | Π = t] Pr [Π = t]
t

≥

≥

X

bad t

X

Pr [error | Π = t] Pr [Π = t]

(1/20) · Pr [Π = t] = Pr [Π is bad] /20.

bad t

The claim follows.
29

Next, say that t is informative if:
X

e∈U ×V1 ∪U ×V2

∆t (e) ≥ 10αn1/4 .

Lemma 4.9. Pr [Π is informative] ≤ 1/10.
Proof. By super-additivity,
αn1/4 = |Π| ≥ I(Π; E 1 ∪ E 2 )
X
I(Π; X e )
≥
e∈U ×V1 ∪U ×V2



= E 

X

D (π(X e |Π = t) k π(X e ))

≥ E 

X

∆t (e) .

t∼Π

t∼Π

The claim follows by Markov.



e∈U ×V1 ∪U ×V2



e∈U ×V1 ∪U ×V2



(By Lemma 4.3)

Corollary 4.10. There exists a transcript which is both good and uninformative.
Proof. By union bound, the probability that a transcript is either not good or informative is at most 20δ +
1/10 < 1.
We will now show that such a transcript cannot exist, as an uninformative transcript cannot cover enough
edges to be good.
For any particular transcript t of Π, the inputs of the three players remain independent given Π = t.
Therefore, for any edge (v1 , v2 ) ∈ V1 × V2 ,
X
Pr [∃u : (u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | Π = t] ≤
Pr [(u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | Π = t]
u∈U

=

X

u∈U

=

X

u∈U

=

X

u∈U

(Pr [(u, v1 ) ∈ E 1 ] Pr [(u, v2 ) ∈ E 2 | Π = t])

√ 
√ 
∆t (u, v1 ) + 2γ/ n ∆t (u, v2 ) + 2γ/ n

√ X
(∆t (u, v1 )∆t (u, v2 )) + 2(γ/ n)
(∆t (u, v1 ) + ∆t (u, v2 )) .
u∈U

√
Now let t be a transcript that is good, that is, |C (t) | ≥ n/(2γ), and also uninformative. Let S(t) ⊆
√
C (t) be a set of n/(2γ) covered edges (chosen arbitrarily from C (t)), and let W1 (t) ⊆ V1 and W2 (t) ⊆ V2
be the endpoints of the edges in S. Since each edge (v1 , v2 ) ∈ S(t) is covered in t,
X
√ X
(∆t (u, v1 )∆t (u, v2 )) + 2(γ/ n)
(∆t (u, v1 ) + ∆t (u, v2 )) ≥ 9/10,
u∈U

u∈U

30

and together we have
X

X

(v1 ,v2 )∈S(t) u∈U

"

√ X
(∆t (u, v1 )∆t (u, v2 )) + 2(γ/ n)
(∆t (u, v1 ) + ∆t (u, v2 ))
u∈U

√
≥ (9/10)|S| = (9/20) n/γ.

#

On the other hand,
"
#
X
X
√ X
(∆t (u, v1 )∆t (u, v2 )) + 2(γ/ n)
(∆t (u, v1 ) + ∆t (u, v2 ))

(v1 ,v2 )∈S(t) u∈U

≤



X
√
∆t (u, v2 ) + 2(γ/ n)

∆t (u, v1 ) 

X

X X

∆t (u, v1 ) 

X X

u∈U

≤

u∈U



X

X






v1 ∈V1

u∈U v1 ∈V1

v2 ∈V2



u∈U v2 ∈V2



√
+ 2(γ/ n) · |S(t)| · 

X X

u∈U v1 ∈V1

We therefore have





∆t (u, v1 ) + 

2

√
√
≤ 10αn1/4 + 2(γ/ n) · n/(2γ) · 10αn1/4
√
≤ (100α2 + 10α) n.

(∆t (u, v1 ) + ∆t (u, v2 ))

v1 ∈C1 (t) v2 ∈C2 (t)



∆t (u, v2 )

X

X X

u∈U v2 ∈V2



∆t (u, v2 )

√
√
(100α2 + 10α) n ≥ (9/20) n/γ,

contradicting our assumption about α.
Streaming Lower Bounds There is a known connection between communication complexity, specifically,
one-way communication, and space complexity in the data-stream model. In this model the input arrives as
an ordered sequence that must be accessed in order and can be read only once, while the space complexity is
defined as the maximal size of the memory used at any given point of the computation. As demonstrated in
[4], there is a generic reduction which proves that lower bounds on the one-way communication complexity
of a problem, are also lower bounds on the space-complexity of the same problem in the data-stream model.
Consequently, we get a corresponding lower bound of Ω(n1/4 ) on the space complexity of detecting a
triangle edge (with the input graph distribution identical to the one in our model) in the data-stream model.
We present here a sketch of the proof, as the data-stream model is not the focus of this work; for more
details on the relationship between lower bounds in the two models refer to [4, 20].
Assume to the contrary that there exists an algorithm, A, that solves the triangle-edge detection with
space complexity o(n1/4 ) in the data-stream model. This implies a one-way 3-player protocol, Π, of complexity o(n1/4 ), which implies a contradiction (our ”extended” one-way model is even more powerful than
the more standard one-way model used in this reduction, where Alice sends one message to Bob, who then
sends one message to Charlie, who has to output the answer), proving our initial assumption to be false.
More concretely, Π entails Alice running A on the input, which is viewed as the beginning of the stream,
31

then sending the content of the memory (which is limited by o(n1/4 ) bits) to Bob, who continues the computation of A on his input, which is viewed as the continuation of the stream, and once again sends the
content of the memory to Charlie, who concludes the computation of A on his input, the final segment of
the stream.
We can apply the same reduction to the extended one-way lower bounds we derive later in this chapter
√
for a more general average degree d = O( n).
4.2.3

Simultaneous Communication

For simultaneous protocols, it is not enough to have some covered edge that also appears in Charlie’s input:
the referee needs to know (or believe) that it is in Charlie’s input — that is, with good probability, the edge
the referee outputs has a large posterior probability of being in Charlie’s input, given Charlie’s message.
Say that edge e is reported by a transcript t if PrE∼µ|t [e ∈ E] ≥ 9/10. The goal of the players is to
provide the referee with some edge that is covered by Alice and Bob and also reported by Charlie.
We show that the “best” strategy for the players is to choose a set T ⊆ V1 × V2 of Θ(n) edges, and have
Alice and Bob try to cover edges from T and Charlie report edges from T . The crux of the lower bound is
showing that to target a fixed set of edges T , Alice and Bob must give up their quadratic advantage: whereas
in for in our analysis of the one-way lower bound, the sum P
of the cover probabilities was bounded by the
square of the sum-increase of individual edge probabilities ( e ∆t (e)), here we show that we can bound it
√
linearly, yielding a lower bound of Ω( n) instead of Ω(n1/4 ).
Fix a deterministic simultaneous protocol Π, where the messages sent by the three players are M 1 , M 2
and M 3 , respectively. Let Π(m1 , m2 , m3 ) denote the edge output by the referee upon receiving messages
m1 , m2 and m3 from the three players. We freely interchange the messages with the inputs to the respective
players, since the protocol is deterministic; e.g., we write Π(E 1 , E 2 , E 3 ) to indicate the referee’s output
upon receiving the messages sent by the players on input (E 1 , E 2 , E 3 ).
√
Let C = α n be the number of bits sent by each player, where α will be fixed later. Let δ denote the
error of Π on µ. Our goal is to show that when γ and δ are sufficiently small, we require α = Ω(1), so the
communication complexity of the protocol is Ω(n).
In a simultaneous protocol, the messages sent by the players are independent of each other given the
input. In our case, because the inputs are also independent of each other, the messages are independent
even without conditioning on a particular input. We therefore abuse notation slightly by omitting parts
of the transcript that are not relevant to the event at hand. Specifically, we let Rep(mi ) denote the set of
edges covered by a message mi of player i (this is independent of the other players’ messages), and we
let C (m1 , m2 ) denote the edges covered by messages m1 , m2 of Alice and Bob, respectively (again, this
is independent of Charlie’s message). We also sometimes write the player’s input instead of its message;
because the protocol is deterministic, the message is a function of the input.
In any simultaneous protocol, the goal of the players is to provide the referee with an edge in Charlie’s
input that is both reported by Charlie and covered by Alice and Bob:
Lemma 4.11. The probability that there exists an edge that is both reported by Charlie and covered by Alice
and Bob is at least 1 − 10δ. That is,
Pr [Rep(M 3 ) ∩ C (M 1 , M 2 ) 6= ∅] ≥ 1 − 10δ.
Proof. If the referee outputs an edge that is both covered and reported, then of course there must exist such
an edge. Let us therefore bound the probability that the referee outputs an edge that is either not reported
32

or not covered. Call a triplet (m1 , m2 , m3 ) of messages “bad” if Π(m1 , m2 , m3 ) = e, where e is either not
reported (e 6∈ Rep(m3 )) or not covered (e 6∈ C (m1 , m2 )).
The protocol errs whenever it outputs an edge e ∈ E3 that is not in Charlie’s input E 3 , or an edge that
does not form a triangle together with some node u ∈ U . If e is not reported (in m3 ), then Pr [e ∈ E 3 | M 3 = m3 ] <
9/10, and if e is not covered (in m1 , m2 ), then Pr [∃u ∈ U : (u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | M 1 = m1 , M 2 = m2 ] <
9/10. Therefore, each bad triplet of messages contributes at least 1/10 to the error probability of the protocol. Together we have
X
δ ≥ Pr [Π errs] ≥
Pr [(M 1 , M 2 , M 3 ) = (m1 , m2 , m3 )] · (1/10)
bad (m1 , m2 , m3 )

= Pr [ (M 1 , M 2 , M 3 ) are bad] /10.
The claim follows.
By Lemma 4.11, we see that the players’ “best strategy” is to try to “coordinate” the edges reported by
Charlie with the edges covered by Alice and Bob, so that the referee can find an edge in the intersection.
Indeed, as a corollary we obtain:
hP
i
Corollary 4.12. E
Pr[Cov
(e)]
≥ 1 − 10δ.
e∈Rep(E 3 )

Proof. Fix Rep(E 3 ) = R. By union bound and the independence of the players’ inputs,
X
X
Pr [e ∈ C (M 1 , M 2 )] =
Pr [Cov (e)]
Pr [R ∩ C (M 1 , M 2 ) 6= ∅ | Rep(E 3 ) = R] ≤
e∈R

e∈R

Therefore,


X

E

e∈Rep(E 3 )

=

X
R

≥
≥

X
R

X
R

 



Pr[Cov (e)]

E 

X

e∈Rep(E 3 )

X

e∈R





Pr[Cov (e)] | Rep(E 3 ) = R Pr [Rep(E 3 ) = R]
!

!

Pr [Cov (e)] Pr [Rep(E 3 ) = R]

(Pr [R ∩ C (M 1 , M 2 ) 6= ∅ | Rep(E 3 ) = R] Pr [Rep(E 3 ) = R]) ≥ 1 − 10δ.

Analyzing Charlie’s messages. First, observe that Charlie (and the other players) cannot report too many
edges, except with small probability. Each reported edge is “a little expensive”:
Lemma 4.13. Let mi be a message sent by player i. Assume that γ < 1/2. If e ∈ Rep(mi ), then for
sufficiently large n we have D (π(X e | M i = mi ) k π(X e )) ≥ 9 log n/40.
33

√
Proof. Since e ∈ Rep(mi ), the posterior probability that X e = 1 is at least 9/10 > γ/ n. Because
D (p k q) increases as |p − q| increases, for sufficiently large n,
√ 
D (π(X e | M i = mi ) k π(X e )) ≥ D 9/10 k γ/ n
9/10
1/10
√
= (9/10) log √ + (1/10) log
γ/ n
1 − γ/ n
√
1
n
√
+ (1/10) log
= −H(1/10) + (9/10) log
γ
1 − γ/ n
9
9/10
log n ≥
log n.
≥ −1 +
2
40
√
We used the fact that γ < 1/2, so (9/10) log(1/γ) > 0, and also that 1 − γ/ n < 1, and hence log(1/(1 −
√
γ/ n)) > 0.
It follows that with a budget of C bits, Charlie can only report roughly C edges (in fact, somewhat less)
in expectation:
Corollary 4.14.
E [|Rep(E 3 )|] ≤

40α √
n
9 log n

Proof. By the super-additivity of information,
X
√
α n = |M3 | ≥ I(M 3 ; E 3 ) ≥
I(M 3 ; X e )
e∈E3

=

≥
≥

E



E



E



m3 ∼M 3

m3 ∼M 3

m3 ∼M 3





X

e∈E3



D (π(X e | M 3 = m3 ) k π(X e ))

X

e∈Rep(m3 )



D (π(X e | M 3 = m3 ) k π(X e ))


9
log n .
|Rep(m3 )| ·
40

The claim follows.
As we said above, since the referee “wants” to output an edge that is both reported and covered, the goal
of the players should be to provide it with such an edge. Let us rank the edges in V1 × V2 according to the
probability that they are covered by Alice and Bob: we write V1 × V2 = {e1 , . . . , en2 }, where i ≤ j iff
Pr [Cov (ei )] ≥ Pr [Cov (ej )], breaking ties arbitrarily.
Let Top(E 3 ) denote the set of |Rep(E 3 )| highest-ranking edges in E 3 . Clearly,
X
X
Pr [Cov (e)] ≤
Pr [Cov (e)] .
(6)
e∈Rep(E 3 )

e∈Top(E 3 )

That is, “it is in Charlie’s interest” to report edges from Top(E 3 ), as this maximizes the probability that
some reported edge is also covered.
34

Let T = {e1 , . . . , em } be the m highest-ranking edges in V1 × V2 , where
9
n.
80α

m=
For any integer k ≥ 1 we have:
X

e1 ,...,ek·m

Therefore,


X
Pr[Cov (e)]
E

Pr [Cov (e)] ≤ k ·

X

Pr [Cov (e)] .

e∈T

e∈Rep(E 3 )



≤ E
=

X

e∈Top(E 3 )

⌉ log(n2 /m)⌉

X
i=1

≤

⌉ log(n2 /m)⌉

X
i=1

Pr[Cov (e)]



E

"



X

e∈Top(E 3 )

2i+1 ·

X





Pr[Cov (e)] 2i · m ≤ |Top(E 3 )| ≤ 2i+1 · m Pr 2i · m ≤ |Top(E 3 )| ≤ 2i+1 · m
!

Pr [Cov (e)]

e∈T

√ X
n
40α
≤ log n · 2 ·
·
Pr [Cov (e)]
9 log n m
e∈T
P
Pr [Cov (e)]
.
= e∈T √
n
Analyzing the cover probabilities

E [|Top(E 3 )|]
·
2i · m

#

(7)

We show that it is not possible for the two other players to have:
X
√
Pr [Cov (e)] ≥ β · n,
e∈T

where β is a constant whose value will be fixed later.
√
Notation. Let V H be the set of nodes in V1 ∪ V2 whose degree in T is at least n, and let V L be the
remaining nodes in V1 ∪ V2 . Also, let Via = V a ∩ Vi , for a ∈ {L, H} and i ∈ {1, 2}.
√
9
.
Since |T | ≈ n, we have |V H | ≤ c · n, where c = 80α
Let T1 = V1L × V2 ∪ V1 × V2H and let T2 = V1 × V2L ∪ V1H × V2 . For edges in T1 , their endpoints in V1
√
all have low degree in T1 (edges in V1L × V2 have degree at most n in T , and edges in V1 × V2H also have
√
low degree in T1 , since |V H | ≤ c · n). We have T = T1 ∪ T2 , so it suffices to bound the sum of the cover
probabilities in T1 and the sum in T2 . (The union is not disjoint; e.g., edges in V1L × V2L appear in both sets,
so we may be over-counting). Let NS (v) denote the nodes adjacent to node v in S ⊆ V1 × V2 .
We let M 1 , M 2 be random variables denoting the messages sent by the two players, respectively. Let
M1 , M2 be the set of all possible messages for each player (resp.).
35

Bounding the cover probabilities in T . For any pair of messages m1 , m2 , if e = (v1 , v2 ) ∈ C (m1 , m2 ),
then by union bound,
X
Pr [(u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | M 1 = m1 , M 2 = m2 ]
u∈U

≥ Pr [∃u : (u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | M 1 = m1 , M 2 = m2 ] ≥ 9/10.

(8)

Because the edges in E 1 and E 2 remain independent given M 1 = m2 , M 2 = m2 , and the messages are
also independent of each other and of the other player’s input, for each u ∈ U ,
Pr [(u, v1 ) ∈ E 1 ∧ (u, v2 ) ∈ E 2 | M 1 = m1 , M 2 = m2 ]

= Pr [(u, v1 ) ∈ E 1 | M 1 = m1 , M 2 = m2 ] · Pr [(u, v2 ) ∈ E 2 | M 1 = m1 , M 2 = m2 ]

= Pr [(u, v1 ) ∈ E 1 | M 1 = m1 ] · Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] .

Consider first the edges in T1 . Plugging the above into (8), and also writing Pr [(u, v1 ) ∈ E 1 | M1 = m1 ] =
√
∆m1 (u, v1 ) + 2γ/ n (where ∆m1 is the L1 difference between the posterior and the prior), we obtain:
X

√ 
∆m1 (u, v1 ) + 2γ/ n Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] ≥ 9/10.
(9)
u∈U

Multiplying both sides by Pr [M 2 = m2 ], and summing across all m2 such that (v1 , v2 ) ∈ C (m1 , m2 ), we
get that for any m1 ,
X
X

√ 
∆m1 (u, v1 ) + 2γ/ n · Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] Pr [M 2 = m2 ]
m2 :(v1 ,v2 )∈C(m1 ,m2 ) u∈U

=

X

u∈U

≥ (9/10)

! 
√ 
∆m1 (u, v1 ) + 2γ/ n · 
X

X

m2 :(v1 ,v2 )∈C(m1 ,m2 )

Pr [M 2 = m2 ]

Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] Pr [M 2 = m2 ]

m2 :(v1 ,v2 )∈C(m1 ,m2 )

= (9/10) Pr [Cov (v1 , v2 ) | M 1 = m1 ] .
Notice that for any u ∈ U ,
X

m2 :(v1 ,v2 )∈C(m1 ,m2 )

≤

X

m2 ∈M2

Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] Pr [M 2 = m2 ]

Pr [(u, v2 ) ∈ E 2 | M 2 = m2 ] Pr [M 2 = m2 ]

√
= Pr [(u, v2 ) ∈ E 2 ] = γ/ n.
Therefore,
X

u∈U

√ 
∆m1 (u, v1 ) + 2γ/ n

!

√
· (γ/ n) ≥ (9/10) Pr [Cov (v1 , v2 ) | M 1 = m1 ] .

36



Now, taking the expectation over all m1 ,
"
#
X
√
√
(∆M 1 (u, v1 ) + 2γ/ n) ≥ (9/10) E [Pr [Cov (v1 , v2 ) | M 1 ]]
γ/ n E
M1

M1

u∈U

= (9/10) Pr [Cov (v1 , v2 )] .

√
Summing across all v2 such that (v1 , v2 ) ∈ T1 , and using the fact that the degree of v1 in T1 is at most c· n,
"
#
"
#!
X
X
X
√
√
√
√
√
c n · γ/ n E
(∆M 1 (u, v1 ) + 2γ/ n) ≥
(∆M 1 (u, v1 ) + 2γ/ n)
γ/ n E
M1

≥ (9/10)

u∈U

X

v2 ∈NT1 (v1 )

M1

u∈U

Pr [Cov (v1 , v2 )] .

v2 ∈NT1 (v1 )

And now, summing over all v1 ∈ V1 ,


X X
X
√
∆M 1 (u, v1 ) + 2γ/ n
E 
cγ
v1 ∈V1



M1

v1 ∈V1 u∈U



= cγ  E 
M1

X X

v1 ∈V1 u∈U

Using Lemma 4.6 we obtain:





√
∆M 1 (u, v1 ) + 2γ n ≥ (9/10)
X

e∈T1

Pr [Cov (e)] ≤

X

Pr [Cov (v1 , v2 )] .

(v1 ,v2 )∈T1 )

cγ(α + 2) √
n.
9/10

For edges in T2 the argument is symmetric.
Together we have:
X
e∈T

Pr [Cov (e)] ≤

√
1
2cγ(α + 2) √
n ≤ (α + 2) n,
9/10
25

assuming that γ is a sufficiently small constant.
Combining this with (7), we see that we must have α ≥ 23/25.

4.3 Lifting 3-player Lower Bounds to k Players
Using symmetrization [33], we “lift” our lower bounds for a constant number of players to general kplayer lower bounds (Symmetrization was developed in [33] to lift unrestricted 2-player lower bounds to
unrestricted k-player lower bounds.) Interestingly, our symmetrization reduction transforms a simultaneous k-player protocol into a one-way 3-player (or 2-player) protocol, so in order to obtain lower bounds
on simultaneous protocols for k players we need to first prove lower bounds on one-way protocols for a
small number of players. This curious behavior turns out to be inherent, at least for large k: a simultaneous protocol can emulate a one-way protocol, by having each player send their entire input to the referee
with probability 1/k, and otherwise send their message under the one-way protocol. The referee can, with
constant probability, take the role of one of the players, whose input the referee received, and compute the
37

answer using the messages from the other players. When k is sufficiently large, this may be cheaper than
the simultaneous protocol.
We say that a k-player distribution µ is symmetric if the marginal distribution of each player’s input is
the same.
Theorem 4.15. Let P be a graph property, Suppose that µ is a symmetric 3-player input distribution such
k,sim
ǫ
ǫ
that CC3,→
µ,δ (P ) = C. Then there is a k-player input distribution η such that CCη,δ (P ) ≥ (k/2)C.
Proof. Let η be the following distribution: we sample (X 1 , X 2 , X 3 ) ∼ µ; we give X 1 and X 2 to two
random players that are not player k, and the remaining players all receive X 3 .
We show by reduction from the 3-player case that η is hard for k players. Let Π be a simultaneous
protocol for k players that solves P ǫ on η with error probability δ.
We construct a 3-player protocol Π′ as follows: Alice and Bob publicly choose two random IDs i, j ∈ [k]
(i 6= j), and take on the roles of players i and j, using their actual inputs under µ. Charlie will play the role
of all the remaining players, using his input for each one of them, and also the role of the referee (who has
no input). Let embed(i, j, X) denote the input thus constructed, where X = (X1 , X2 , X3 ). The resulting
k-player input distribution is exactly η.
To simulate the execution of Π, Alice and Bob simply send Charlie the messages players i and j would
send under Π to player k. Charlie computes the messages that each player ℓ ∈ [k] \ {i, j} would send,
and then, using these messages and the messages received from Alice and Bob, computes the output of the
referee.
The simulation adds no error — on each input, it exactly computes the referee’s output (or rather, it
generates the correct distribution for the referee’s output). Therefore,

 X


µ(X) Pr Π′ errs on X
Pr Π′ errs =
µ

X



X
X
1
Pr [Π errs on embed(i, j, X)]
µ(X) 
=
k(k − 1)
i,j
X
X
=
η(Y ) Pr [Π errs on Y ] ≤ δ.
Y

What is the expected communication of Π′ ? Observe that since Π is simultaneous, each player’s transcript is a (random) function of only its own input: in particular, the distribution of player i’s transcripts is the
same under any joint input distribution where player i’s input has the same marginal. In η, all players’ inputs

38

have the same marginal distribution — the marginal distribution of each player’s input in µ. Therefore,


E
[|Π(embed(i, j, X))|]
E |Π′ (X)| =
X∼µ

i,j∼U [k],X∼µ

=

=
=

E

[|Πi (embed(i, j, X))| + |Πj (embed(i, j, X))|]

E

[|Πi (Y )| + |Πj (Y )|]

i,j∼U [k],X∼µ
i,j∼U [k],Y ∼η

E

i∼U [k],Y ∼η

[|Πi (Y )|]

k
1X
E [|Πi (Y )|]
Y ∼η
k
i=1
#
" k
X
2
2
=
E
|Πi (Y )| = CC(Π).
Y
∼η
k
k

=2

i=1

This result implies a Ω(k · n1/4 ) lower bound for the problem of k players trying to find a triangle-edge
√
in a graph of average degree d = Θ( n) via simultaneous communication,
For deterministic and symmetric protocols we can do a little better, by modifying the reduction: instead
of constructing a one-way protocol, we construct a simultaneous protocol — using the fact that the original
k-player protocol is deterministic, Charlie can pick one of the players he simulates and send the message of
only that one player to the referee, because we know that all the players simulated by Charlie will send the
same message (as they receive the same input).

4.4 Lower Bound for Degree O(1)
For graphs with average degree O(1), a lower bound was shown in the streaming model in [27] reducing the
Hidden Boolean Matching problem, introduced in [28] to triangle counting approximation in streaming. The
same reduction yields a lower bound on triangle testing in two players one-way communication complexity.
We present the reduction for the sake of completeness, and to show that it indeed holds in our model as well.
We use the bound shown in [36] but need only the bound for matchings (rather than hypermatchings),
we give here a simplified version of the problem;
Definition 12 (Boolean Matching). In the Boolean Matching problem, denoted BM n , Alice receives a vector
x ∈ {0, 1}2n , and Bob receives a perfect matching M on 2n vertices {1, . . . , 2n} and a vector w ∈ {0, 1}n .
We represent M as an n × 2n matrix, where each row represents one edge of the matching: if the i-th edge
of the matching is {j1 , j2 } ⊆ [2n]2 , then the i-th row of the matrix contains 1 in columns j1 and j2 , and 0
elsewhere.
The goal of the players is to distinguish the case where
→
−
Mx ⊕ w = 0
from the case where

→
−
Mx ⊕ w = 1 .

Theorem 4.16. The randomized one-way communication complexity of testing triangle-freeness in graphs
√
with average degree O(1) is Ω( n).
39

Proof. Given inputs X for Alice and M, w for Bob, the players construct the following graph G = (V, E),
where V = {u} ∪ ([n] × [2]):
• For each bit i ∈ [n] where xi = 0, Alice adds the edge {u, (i, 0)}; for each bit i ∈ [n] where xi = 1,
she adds the edges {u, (i, 1)}.
• For each edge ej = {j1 , j2 } in his matching,
– If wj = 0, Bob adds edges {(j1 , 0), (j2 , 0)} and {(j1 , 1), (j2 , 1)};

– If wj = 1, Bob adds edges {(j1 , 0), (j2 , 1)} and {(j1 , 1), (j2 , 0)}.

For each j ∈ [n], let Mj = {j1 , j2 }.
A triangle appears in the subgraph induced by vertices {u, (j1 , 0), (j1 , 1), (j2 , 0), (j2 , 1)} iff either wj =
0 and xj1 = xj2 , or wj = 1 and xj1 6= xj2 . In other words, a triangle appears iff (M x ⊕ w)j = 0. No other
→
−
triangles appear in the graph. Therefore, if M x ⊕ w = 0 then G contains n edge-disjoint triangles, and if
→
−
M x ⊕ w = 1 then G is triangle-free. In the first case, G is 1-far from triangle-freeness.

4.5 Other Degrees
We now show how we can extend a lower bound for a given average degree, d, to any lower degree, d′ , by
embedding dense inputs of degree d into sparse graphs such that the average degree evens out to be d′ .
Lemma 4.17. Let d = Θ(nc ) denote the average degree of the graph, and let CC(T ǫ,d,n ) = Θ(f (n)) denote
the communication complexity as a function of n, the number of vertices. Then for any d′ ≤ d, we have
1
′
CC(T ǫ,Θ(d ),n ) = Θ(f ((d′ n) 1+c )).
1

Proof. For graphs with n′ = (d′ n) 1+c vertices and average degree Θ((n′ )c ), the communication complexity
is Θ(f (n′ )). We examine the following subset of graphs with n vertices and average degree d′ : any such
graph, G, is a union of (n − n′ ) isolated nodes, and a graph, G′ , which is either triangle-free or ǫ-far from
′
being triangle-free, and has n′ vertices and average degree (n′ )c . The average degree of G is Θ((n′ )c ) · nn =
Θ(d′ ), and its distance to being triangle-free is identical to that of G′ , as it has no edges outside of G′ .
Since any triangle in G must be contained in G′ , solving the problem on G is equivalent to solving it on
G′ . And since we asserted that the complexity of the problem for graphs with the stated properties of G is
1
Θ(f (n′ )) = Θ(f (d′ n) 1+c , it is also the complexity of the problem for graphs of average degree Θ(d′ ).
Note that lemma 4.17 holds regardless of the model of communication. Therefore, as a corollary, we
√
√
can generalize the lower bounds we derived directly for graphs of average degree n to d = O( n) (for 3
√
players in both cases). Specifically, the Ω(n1/4 ) bound for one-way communication and the Ω( n) bound
for simultaneous communication extend to Ω((nd)1/6 ) and Ω((nd)1/3 ), respectively. Furthermore, lemma
4.17, combined with theorem 4.15 and the lower bounds we proved in section 4.2 imply Theorem 4.1, the
main result of this section.

4.6 Discussion: Lower Bounds on the Communication Complexity of Property-Testing
Lower bounds on the “canonical” problems in communication complexity, such as Set Disjointness and Gap
Hamming Distance [12], cannot be leveraged to obtain property-testing lower bounds, at least for trianglefreeness. Some classical problems do feature a gap, where we are only interested in distinguishing two
cases that are “far” from each other; however, for property-testing lower bounds, the gap needs to be around
40

zero (either we have no triangles, or we have many edge-disjoint triangles), while existing gap problems
typically become easy unless the gap is centered far from zero (for example, in Gap Hamming Distance, the
players get vectors x, y ∈ {0, 1}n , and they need to determine whether their Hamming distance is greater
√
√
than n/2 + n or smaller than n/2 − n). In addition, because triangles are not “independent” of each
other (if they share an edge), the direct sum approach to proving lower bounds, which works well when we
can break the problem up into many independent pieces, does not apply here.

5 Summary
In this work we showed that in the setting of communication complexity, property testing can be significantly
easier than exactly testing if the input satisfies the property: exactly determining whether the input graph
contains a triangle was shown to require Ω(knd) bits in [38], but we showed that weakening the requirement
to property-testing improves the complexity, and even simultaneous protocols can do better than the best
exact algorithm with unrestricted communication. However, the problem does not appear to become trivial,
as shown by our lower bounds for simultaneous and restricted one-way protocols. Table 1 summarizes our
main results.
√
√
d = Θ(1) d = O( n) d = Ω( n)
△-freeness
√
Õ(k 4 nd + k2 )
Unrestricted Communication
Upper bound
△-freeness
√
√
Õ(k n)
Õ(k 3 nd)
Simultaneous Communication
Upper bound
△-edge detection
√
”Extended” One-Way Communication
Ω( 6 nd)
—
3 players
Lower bound
△-edge detection
√ 
Simultaneous Communication
Ω 3 nd
—
3 players
Lower bound
△-edge detection
 √ 
Ω k · 6 nd
—
Simultaneous Communication
Lower bound
△-freeness
√
Ω( n)
—
Simultaneous Communication
Lower bound
Table 1: Results summary;
We have provided non-trivial upper bounds for the entire relevant degree range for both simultaneous
and unrestricted communication. Our solutions have several desirable qualities. First, they can overcome
the obstacle of not knowing the average degree in advance. Additionally, the algorithms solve not only the
problem of triangle-freeness, but more specifically, the problem of triangle detection, which can only be

41

harder. Finally, all solutions have a one-sided error - a graph is found to contain triangles only if a triangle is
detected with probability 1. We also address other variants and relaxations, such as the case where all inputs
are disjoint, or a case where the players communicate via a blackboard visible to everyone, and describe
how these guarantees can improve the complexity. In terms of more general contributions, we describe how
to efficiently implement typical building blocks used in standard property-testing solutions, of which the
most notable is the proposed procedure for approximating a vertex degree up to a constant, which can be
used to solve the more general problem of approximating the number of distinct elements in a set.
The task of proving non-trivial lower bounds for triangle-freeness is considerably harder. We have discussed the shortcomings of mainstream techniques in communication complexity for tackling this problem.
Nevertheless, we have been able to produce a a tight lower-bound for the closely related problem of triangle√
edge detection for d = Θ( n) in the simultaneous model. We have also been able to prove a lower-bound
for an extended variation of one-way communication, which enabled us to derive a bound for k players.
Moreover, we showed how to extend these bounds, by a rather generic procedure, to lower average degrees.
Finally, we demonstrated how to translate our one-way bounds into streaming-lower bounds, once again via
a generic (and well known) reduction.
We believe that extending the lower bounds to protocols with unrestricted rounds, and strengthening
them to apply to testing triangle-freeness rather than finding a triangle edge, will require techniques from
Fourier analysis, like the ones used in [28] to show the lower bound on Boolean Hidden Matching (from
which we reduce in Section 4.4). In addition, we believe that devising a hard distribution for dense graphs of
√
degree d = ω( n), with desirable properties for proving lower bounds, will require some sophisticated utilization of Behrend graphs [3]. Finally, a worthwhile topic for related future research could be generalizing
our techniques for detecting a wider class of subgraphs or testing other properties, relying on the propertytesting relaxation. As demonstrated by this work, this relaxation can significantly reduce the complexity
of an otherwise maximally hard problem, but not to a degree that it becomes trivial and uninteresting, as
suggested by our lower bounds. More generally, there is much room for a more elaborate investigation of
the interrelation between the models of communication complexity and property-testing, as alongside innate
distinctions there seem to exist non-trivial similarities the extent of which is yet to be determined.

Acknowledgements
We thank Noga Alon, Eldar Fischer and Dana Ron for fruitful discussions.

References
[1] Noga Alon. Testing subgraphs in large graphs. Random Struct. Algorithms, 21(3-4):359–370, October
2002.
[2] Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs.
Combinatorica, 20(4):451–476, 2000.
[3] Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness in general
graphs. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm,
SODA ’06, pages 279–288, 2006.

42

[4] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency
moments. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing,
STOC ’96, pages 20–29, 1996.
[5] Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs. In Proceedings of the Thirty-fifth
Annual ACM Symposium on Theory of Computing, STOC ’03, pages 700–709, 2003.
[6] Christos Boutsidis, David P. Woodruff, and Peilin Zhong. Optimal principal component analysis in
distributed and streaming models. In Proceedings of the 48th Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 236–249, 2016.
[7] Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Computing, 24(2):79–89, 2011.
[8] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A tight
bound for set disjointness in the message-passing model. In Proceedings of the 2013 IEEE 54th Annual
Symposium on Foundations of Computer Science, pages 668–677, 2013.
[9] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In
Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pages 1011–1020,
2016.
[10] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In Distributed Computing: 30th International Symposium, DISC
2016, Paris, France, September 27-29, 2016. Proceedings, pages 43–56, 2016.
[11] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka
Suomela. Algebraic methods in the congested clique. In Proceedings of the 2015 ACM Symposium on
Principles of Distributed Computing, PODC ’15, pages 143–152, 2015.
[12] Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of
gap-hamming-distance. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 51–60, 2011.
[13] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). 2006.
[14] Danny Dolev, Christoph Lenzen, and Shir Peled. ”tri, tri again”: Finding triangles and small subgraphs
in a distributed setting. In Proceedings of the 26th International Conference on Distributed Computing,
DISC’12, pages 195–209, 2012.
[15] Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In
Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, pages
367–376, 2014.
[16] Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear
time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley,
CA, USA, 17-20 October, 2015, pages 614–633, 2015.

43

[17] Eldar Fischer. The art of uninformed decisions. Bulletin of the EATCS, 75:97, 2001.
[18] Jacob Fox. A new proof of the graph removal lemma. Annals of Mathematics, pages 561–579, 2011.
[19] Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of excluded subgraphs. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, pages 342–356, 2016.
[20] Anna Gál and Parikshit Gopalan. Lower bounds on streaming algorithms for approximating the length
of the longest increasing subsequence. SIAM J. Comput., 39(8):3463–3479, 2010.
[21] Oded Goldreich. Combinatorial property testing – a survey. Randomization Methods in Algorithm
Design, page 4560, 1998.
[22] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and
approximation. J. ACM, 45(4):653–750, 1998.
[23] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. In Proceedings of the
Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 406–415, 1997.
[24] Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Struct.
Algorithms, 23(1):23–57, 2003.
[25] L. Gugelmann. Testing trinagle-freeness in general graphs: Lower bounds. Bachelor thesis, Dept. of
Mathematics, ETH, Zurich, 2006.
[26] Zengfeng Huang and Pan Peng. Dynamic graph stream algorithms in o(n) space. In 43rd International
Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy,
pages 18:1–18:16, 2016.
[27] John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of
the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona,
Spain, Hotel Porta Fira, January 16-19, pages 1778–1797, 2017.
[28] Iordanis Kerenidis and Ran Raz. The one-way communication complexity of the boolean hidden
matching problem. Electronic Colloquium on Computational Complexity (ECCC), 13, 2006.
[29] Eyal Kushilevitz and Noam Nisan. Communication Complexity. 1997.
[30] François Le Gall. Further Algebraic Algorithms in the Congested Clique Model and Applications to
Graph-Theoretic Problems, pages 57–70. 2016.
[31] Yi Li, Xiaoming Sun, Chengu Wang, and David P. Woodruff. On the Communication Complexity of
Linear Algebraic Problems in the Message Passing Model, pages 499–513. 2014.
[32] Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett.,
39(2):67–71, 1991.
[33] Jeff M. Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA ’12, pages 486–501, 2012.
44

[34] T. Rast. Testing trinagle-freeness in general graphs: Upper bounds. Bachelor thesis, Dept. of Mathematics, ETH, Zurich, 2006.
[35] Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5(2):73–205, 2009.
[36] Elad Verbin and Wei Yu. The streaming complexity of cycle counting, sorting by reversals, and other
problems. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pages 11–25, 2011.
[37] David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings
of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12, pages 941–960,
2012.
[38] David P. Woodruff and Qin Zhang. When distributed computation is communication expensive. In
Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18,
2013. Proceedings, pages 16–30, 2013.
[39] David P. Woodruff and Qin Zhang. An optimal lower bound for distinct elements in the message passing model. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 718–733, 2014.

45

