Distributed Testing of Conductance∗

arXiv:1705.08174v3 [cs.DC] 19 Oct 2017

Hendrik Fichtenberger†

Yadu Vasudev‡

We study the problem of testing conductance in the setting of distributed computing and give a two-sided tester that takes O(log(n)/(ǫΦ2 )) rounds to decide if
a graph has conductance at least Φ or is ǫ-far from having conductance at least
Φ2 /1000 in the distributed CONGEST model. We also show that Ω(log n) rounds
are necessary for testing conductance even in the LOCAL model. In the case of a
connected graph, we show that we can perform the test even when the number of
vertices in the graph is not known a priori. This is the first two-sided tester in the
distributed model we are aware of. A key observation is that one can perform a
polynomial number of random walks from a small set of vertices if it is sufficient to
track only some small statistics of the walks. This greatly reduces the congestion
on the edges compared to tracking each walk individually.

1. Introduction
Graphs arise as a natural model of many large data sets in applications like examining social networks, and analyzing structural properties of graphs is a fundamental computational
problem. However, using exact algorithms to solve this task is often not an option because
even linear time or space complexity exceeds available resources. Algorithms that compute an
approximate result are more useful in these scenarios. Various frameworks have been studied
to analyze the limits and merits of such algorithms in theory.
Property testing algorithms derive approximate decisions by probing small parts of the input
only. A tester for a graph property P is a randomized algorithm that, with high constant
probability, accepts inputs that have P and rejects inputs that are ǫ-far from having the
property P, that is, at least an ǫ-fraction of the edges has to be modified to make the graph
have the property P. Testing graph properties in the classic, sequential computing model has
been studied quite extensively. Two-sided error testers may err on all graphs, while one-sided
error testers have to present a witness when rejecting a graph. See [11, 12, 14] for introductions
and surveys.
Property testing in the distributed CONGEST model was first studied by Brakerski and
Patt-Shamir [1] and later more thoroughly by Censor-Hillel et al. [2]. In this model, each
vertex of the graph is equipped with a processor that has a unique identifier of size O(log n)
∗

The research leading to these results has received funding from the European Research Council under the
European Union’s Seventh Framework Programme (FP7/2007-2013)/ ERC grant agreement n◦ 307696.
†
TU Dortmund, Dortmund (hendrik.fichtenberger@tu-dortmund.de)
‡
Department of Computer Science and Engineering, IIT Madras, Chennai (yadu@cse.iitm.ac.in)

1

and it knows only its neighboring vertices. The vertices of the graph communicate with each
other in synchronized rounds such that in each round only communication of length O(log n)
is allowed on every edge. Finally, every vertex casts a vote and a decision rule is applied on
all votes to derive the answer of the tester. The complexity measure is the amount of rounds
required to test the property. Edge congestion and round complexity strictly limit the amount
of information on the whole graph that a single vertex can gather.
In [2], it is shown that many one-sided error testers for dense graphs carry over from the
sequential to the distributed setting. Furthermore, tight logarithmic bounds for testing bipartiteness and cycle-freeness in bounded degree graphs are proved. In [8, 10], subgraph-freeness
is studied for subgraphs on at most five vertices, trees and cliques.

1.1. Our Results
In this paper we study the problem of testing conductance of undirected graphs in the distributed model. We present a two-sided error distributed testing algorithm in the CONGEST
model for testing conductance, which is also the first two-sided error distributed tester we are
aware of.
Theorem 1.1. Testing whether a graph G = (V, E) has conductance at least Φ or is ǫ-far
from having conductance at least Φ2 /1000 with two-sided error has complexity O(log(|V | +
|E|)/(ǫΦ2 )) in the CONGEST model.

Our algorithm is based on the idea of the classic tester in [15] for bounded degree graphs,
that is, random walks mix rapidly in graphs with high conductance and they mix slowly for at
least a small fraction of start vertices in graphs that are ǫ-far from having high conductance. In
bounded degree graphs, the discrepancy of the distribution of a random walk and its stationary
distribution is measured by the walk’s collision probability. However, in general graphs the
endpoint distributions weighted by the vertices’ degrees play a major role. This becomes an
obstacle because one has to ensure that vertices of high degree are not missed.
In the distributed model, one has to take care of edge congestion too. Simulating ω(1)
random walks while keeping them distinguishable is very costly. However, one key observation
here is that for approximating the discrepancy, it is sufficient to maintain only some statistics of
the random walks, which reduces the congestion significantly. In particular, one has to transfer
only the number of random walks that pass through an edge for each of a constant number of
start vertices. We exploit this and some other properties of graphs with high conductance.
If the graph is connected, we prove that the size of the input graph is not required to be
known a priori to perform the test. On the other hand, there exists no tester for disconnected
graphs if no prior knowledge of the graph is assumed at all. Since communication between two
connected components is not allowed, we cannot distinguish a graph G with high conductance
from a graph G′ that is composed of two isolated copies of G.
We complement this result by showing that any distributed tester with this gap requires
Ω(log(n + m)) rounds of communication in the (stronger) LOCAL model.
Theorem 1.2. Testing whether a graph G = (V, E) has conductance at least Φ or is ǫ-far
from having conductance at least cΦ2 requires Ω(log(|V | + |E|)) rounds of communication in
the LOCAL model (for constants c, ǫ, Φ).
For the lower bound, we construct two distributions on graphs of high and low conductance
respectively such that the vertices’ neighborhoods of radius Ω(log n) are isomorphic for both.
The idea is that within only O(log n) rounds, all vertices receive the same information up to

2

isomorphism and therefore cannot distinguish between the two distributions. It seems possible
that the distributed algorithm can glean information about the two distributions from the
vertex labels of the subgraphs it has seen. For example, certain sets of labeled subgraphs
might be present in (many of) the graphs with high conductance that are absent in (many
of) the graphs with low conductance. However, we show that this would not give sufficient
information. Since the local views of the vertices have a large overlap, our technique to rule
out this issue differs from the collision-based argument that is often used in the classic setting
of property testing.

1.2. Related Work
In the classic (that is, non-distributed) setting of property testing, the problem of testing
conductance in bounded degree graphs was first studied in [5, 13]. Kale and Seshadhri [15]
√
and Nachmias and Shapira [22] give Õ(Φ−2 n)-query testers that accept graphs that have
conductance at least Φ and reject graphs that are ǫ-far from having conductance at least
Ω(Φ2 ). An algorithm for testing the cluster structure of graphs has been proposed in [6].
Testing conductance in unbounded degree graphs in the stronger rotation map model with
√
query complexity roughly Õ(Φ−2 m) was studied in [18]. Testing conductance properties
restricted to small sets has been studied in [17]. The optimal query complexity for testing
conductance in general graphs of unbounded degree is still open.
We review some results that use related techniques and discuss similarities and differences
compared to our approach. In the CONGEST model, random walks have been analyzed by
Censor-Hillel et al. [2] to design a tester for bipartiteness. The idea there is to perform a
constant number of random walks from every vertex and to test if two such walks intersect in
a cycle of odd length. Therefore, the algorithm needs to keep the exact trace of each of the
random walks. In contrast, we are only interested in the start vertex and the (current) end
vertex of a random walk. As a result we can perform polynomially many random walks from
a constant number of vertices in the graph.
Distributed random walks have been studied in [7] and [21] for computing the mixing time for
random walks starting from a fixed vertex. In particular, [21] show that one can approximate
the mixing time τv of a vertex v in O(τv log n) rounds by running poly(n) random walks v
and comparing their endpoint distribution to the stationary distribution. The graph’s mixing
time τ = maxv τv relates to the conductance by c1 Φ2 / log n) ≤ 1/τ ≤ c2 Φ. A straightforward
approach based on [21] leads to an O(n log2 (n)/Φ2 ) round algorithm for approximating Φ with
a multiplicative gap of Θ(Φ/ log n). In comparison, our tester’s gap does not depend on n and
its complexity is only logarithmic in n. One reason is that if the graph is far from having
conductance Ω(Φ2 ), there exist many vertices with large mixing times compared to the case
that the graph has conductance Φ (see the proof of Theorem 1.1 for details). This is not
necessarily the case if the graph is not ǫ-far from having conductance Ω(Φ2 ).

2. Preliminaries
Let G = (V, E) be a graph and let S, T ⊆ V, S ∩ T = ∅ be sets of vertices. For simplicity, we
denote |V | and |E| by n and m respectively for the graph G at hand. Let d(v) be the degree
of vertex v ∈ V . We write S̄ for the set V \S. The set of vertices in S̄ that are adjacent to
some u ∈ S isPdenoted by Γ(S). The volume of S is the sum of degrees of vertices in S, that
is, vol(S) := v∈S d(v). The cut between S and T is denoted by E(S, T ) = E ∩ (S × T ). For
3

a set S ⊆ V such that vol(S) ≤ vol(S̄), the conductance of S is cond(S) = |E(S, S̄)|/vol(S).
The conductance of G is defined as Φ(G) = minS⊂V cond(S).

2.1. Distributed Computing
In the distributed computational model, a computation network G = (V, E) with a processor
associated to each vertex v ∈ V is given. Each processor v has access to numbered communication channels to its neighbors in G. Additionally, it may have some specific input I(v).
The computation operates in synchronized rounds that are divided into three phases. In each
round, each processor may do some local computation first, then it may send a message to
each of its neighbors, and finally it receives the messages sent from its neighbors.
Definition 2.1 (Distributed Computational Model, DCM). Let G = (V, E) be a graph
and pG = (pv )v∈V with pv : [d(v)] → Γ(v) be a bijective function, that is, an adjacency
list representation of G. Let I : V → {0, 1}∗ be a mapping from the set of vertices to bit
strings. An instance of the distributed computational model on G, pG and I, DCM(G, pG , I),
is defined as follows. Each vertex v ∈ V is a processor that has communication access to
its neighbors pv (1), . . . , pv (d(v)) by ports numbered 1, . . . , d(v). The model operates in synchronized rounds, where each round r consists of three phases: (i) Each vertex performs local
computation, (ii) each vertex v sends a message to its neighbor pv (i), denoted sr (v, i), for all
i ∈ d(v), (iii) each vertex u receives a message from its neighbor pu (j), for all j ∈ d(u). The
distributed computational model DCM is the set of all instances DCM(G, pG , I).

The LOCAL model is the subset of the DCM such that for each vertex v ∈ V , the input
I(v) is only n and a numerical vertex identifier from [nc ] for some universal constant c. The
CONGEST model is the subset of the LOCAL model such that the size of each message sr (v, i)
is restricted to c log n bits.
A distributed network decision algorithm DNDA(A, O) is an algorithm A that is deployed
to the vertices of a DCM to decide a property of an instance of the model. In particular, the
output of A is a single bit, and the final decision is obtained by applying a function O(·) to
the union of all vertices’ answers.
Definition 2.2 (Distributed Network Decision Algorithm). Let A be an algorithm
that takes a bit string as input and outputs a single bit, and let O : {0, 1}∗ → {0, 1} be a
function. When the distributed network decision algorithm DNDA(A, O) is run on an instance
DCM(G, pG , I), a copy of A is deployed to every vertex v with input I(v) and run in parallel
as described in Definition 2.1. We refer to the copy of A deployed to v by Av . When every
vertex vi has terminated its computation with output bit bvi , the decision of DNDA(A, O) is
O(bv1 bv2 · · · bvn ).


2.2. Distributed property testing
A distributed property testing algorithm is a distributed algorithm as defined in Definition 2.2
that accepts graphs that have a property, and rejects graphs that are ǫ-far from the property.
We say that a graph G with n vertices and m edges is ǫ-far from a property P if at least ǫm
edges of G have to be modified to make the new graph have the property P.
A one-sided error distributed ǫ-test accepts all graphs with property P, whereas it rejects,
with probability at least 2/3, all graphs that are ǫ-far from the property. In this paper, we
give a two-sided (error) property tester that is also allowed to err, with probability at most
1/3, when the graph has the property.

4

Definition 2.3 (Two-sided tester). A two-sided (error) distributed ǫ-test for a property P
is a DNDA(A, O), where O(bv1 bv2 · · · bvn ) = 1 iff bvi = 1 for all vi ∈ V such that the following
conditions hold:
• If G has the property P, then, with probability at least 2/3, bvi = 1 for all vi ∈ V .
• If G is ǫ-far from P, then, with probability at least 2/3, there exists a vi ∈ V such that
bvi = 0.

The guarantees given by our tester are actually a bit stronger in the sense that the tester
can be modified such that either bv = 0 or bv = 1 for all v ∈ V simultaneously. See Section 5
for a discussion of the acceptance behavior.

3. Testing Using Random Walks
In this section we will present the distributed algorithm for testing whether a graph has conductance at least Φ or is ǫ-far from having conductance at least Φ2 /1000. The core idea of
the algorithm is to perform random walks from a small set of vertices and test whether these
walks converge to the stationary distribution rapidly, which is the case for graphs with high
conductance. It is based on the ideas of Kale and Seshadhri [15] and Goldreich and Ron [13].
Before we describe the algorithm, we give a few useful definitions and lemmas. A lazy
random walk on a graph G = (V, E) on n vertices is a random walk on the graph, where at
each vertex v the walk chooses to stay at v with probability 1/2 and chooses a neighbor u with
probability 1/(2d(v)). The walk matrix W = [wuv ]u,v∈[n] is defined by wuv := 1/2 if u = v,
wuv := 1/(2d(v)) if u 6= v, (u, v) ∈ E and wuv := 0 otherwise. Notice that for irregular graphs,
W is not symmetric. To analyze these random walks, one can draw on the normalized walk
matrix, which is a symmetric matrix similar to W . The normalized walk matrix N of G is
D −1/2 W D 1/2 , where D is the diagonal matrix with D(u, u) := d(u).
Since N is a real symmetric matrix, it has real eigenvalues. Let 1 = µ1√
, . . . , µn ≥ 0 be its
~ , where π
~ is the
eigenvalues, and let {f~i }i∈[n] be its orthonormal eigenbasis. We have f~1 = π
~ v = d(v)/(2m).
random walk’s stationary distribution. In particular, it is well known that π
For more details on spectral graph theory, refer to [4].
It is well known that graphs with high conductance have small diameter.
Lemma 3.1 ([3, cf. Theorem 2]). Let G = (V, E) be a graph with conductance Φ. The
diameter of G is at most (3/Φ) ln(m).
Sinclair [24] proved that there is a tight connection between the conductance and the mixing
~ after
time of random walks. In particular, the L2 distance of any starting distribution π~′ to π
Φ−2 log n steps is O(1/n).
Lemma 3.2 ([24, cf. Theorem 2.5]). Let G = (V, E) be a graph with conductance Φ. For
ℓ
~ k2 ≤ 1 − Φ2 /2 .
any starting distribution π~′ , it holds that kW ℓ π~′ − π

3.1. Algorithm

We discuss the algorithm from a global point of view instead of describing an algorithm A for
a single vertex to provide a better explanation of the interactions between vertices.
Lemma 3.1 implies that if the graph has high conductance, then it has diameter O(log n),
which we want to use as an assumption in the algorithm later. To test the diameter, we perform

5

a BFS of depth O(log n) of the graph starting from an arbitrary vertex. Initially, every vertex
chooses itself as root of the BFS and announces itself as root to all its neighbors. To break
the symmetry between the vertices, a vertex accepts every vertex with a lower identifier than
its current root as new root and forwards its messages. If the diameter is O(log n), a unique
root has been chosen after O(log n) rounds and every vertex knows its parent and its children
in the BFS tree. Otherwise, at least one of the remaining candidates will reject. Algorithm 3
on page 16 gives a formal description of the BFS.
From now on, assume that the diameter is O(log n). Using the previously computed BFS
tree, we can compute the number of edges in the graph by summing up vertex degrees from
the leaves to the root and transmitting this number to all vertices afterwards. Algorithm 4 on
page 16 describes the procedure in detail.
The key technical lemma from [15] for bounded degree graphs states that if a graph is ǫ-far
from having conductance Ω(Φ2 ), then there exists a Ω(ǫ)-fraction of weak vertices such that
random walks starting from these vertices converge only slowly to the stationary distribution.
Therefore, a sample S ⊂ V of size O(1) will likely contain a weak vertex.1 We extend this
lemma to unbounded degree graphs. Then, we perform N = O(n100 ) random walks of length
ℓ = O(log n) starting from each of the vertices in S to approximate the rate of convergence.
The crucial point here is that in each round of the algorithm, we do not send the full trace of
every random walk. Instead, for every origin v ∈ S, every vertex u ∈ V only transmits the total
number of random walks that are leaving it through an edge (u, w) to its neighbor w ∈ Γ(u).
Since the size of S is constant, we require O(log n) bits per edge to communicate this. On the
other hand, this information is sufficient because we are only interested in the distribution of
endpoints of the lazy random walks for every v ∈ S. Algorithm 2 gives a formal description
of this procedure. Finally, the estimated distribution of endpoints is used to approximate the
distance to the stationary distribution for each v ∈ S. The whole algorithm is summarized in
Algorithm 1.
Algorithm 1 Conductance tester
1: procedure TestConductance(G = (V, E), n, Φ)
2:
BFS(G, 6/Φ ln n)
⊲ construct BFS of depth 6/Φ log n, Algorithm
3:
if BFS visited less than n vertices then reject
4:
m ← AggegrateSum(G, 12/Φ ln n, f )
⊲ f (v) := d(v)/2, Algorithm
5:
let every vertex v ∈ V do
6:
with probability min{1, 104 d(v)/2ǫm}, mark v
7:
S ← marked v, r ← root of BFS tree
8:
if |S| > 105 /ǫ then reject
9:
RandomWalk(G, S, 40/Φ2 · log n, n100 )
⊲ compute local sv,u , Algorithm
10:
for all v ∈ S do sv ← AggegrateSum(G, 12/Φ ln n, f )
⊲ f (u) := sv,u , Alg.
11:
let every vertex v ∈ V do
12:
if sv ≤ m−15 for all v ∈ S then accept
13:
else reject

3
4

2
4

c ℓ of Algorithm 2 are good or the algorithm
First, we show that either the estimates W
v,u
rejects in line 15 because G has low conductance. The proof is given in the appendix.
1

Technically, we sample each vertex v independently into S with probability Θ(d(v)/ǫm). By Markov’s inequality, we may reject if S is much larger than its expected size.

6

Algorithm 2 Perform random walks
1: procedure RandomWalk(G,S,ℓ,N )
2:
let every vertex v ∈ S do
3:
Pv ← {u1 , · · · , uN } where each ui is chosen indep. according to W e~v
4:
for all vertex w ∈ Pv chosen nw times do send (v, nw ) to w
5:
for ℓ rounds, let every vertex v do
6:
if v receives (v1 , n1 ), (v2 , n2 ), · · · , (vk , nk ) then
7:
for all (vi , ni ) do
8:
Pvi ← {u1 , · · · , uni } where uj is picked indep. according to W e~v
9:
for all vertex w ∈ Pvi chosen nw times do append (vi , nw ) to Lw
10:
for all w ∈ Γ(v) do send Lw to w
11:
let every vertex u ∈ V do
12:
if u receives (v1 , n1 ), (v2 , n2 ), · · · , (vk , nk ) then
13:
for all v ∈ S
do
cℓ ← P
14:
W
v,u
vi =v ni /N
ℓ
cv,u ≤ 2m−2 then reject
15:
if W
16:

ℓ )2 − W
ℓ d(v) +
cv,u
cv,u
sv,u ← (W
2m

d(v)2
4m2

Lemma 3.3. Consider Algorithm 2. For every v, u ∈ V , it holds with probability at least
c ℓ < m−2
c ℓ −W ℓ (v, u)| ≤ m−20 and, conditioned on the previous, (ii) if W
1−m−10 that (i) |W
v,u
v,u
then G has conductance less than Φ.

Furthermore, Lemma 3.3 implies that the estimates sv in Algorithm 1 (see line 10) are also
good if Algorithm 2 has not rejected before.

Lemma 3.4. Consider Algorithm 1. With probability at least 1 − m−8 it holds for every v ∈ S
~ k22 − sv ≤ 3m−19 .
in line 10 that kW ℓ (v, ·) − π
Proof. Let v ∈ S. We have the following equality for the discrepancy of the distribution of the
random walks’ endpoints that start at v and the stationary distribution:

X
d(u) d(u)2
ℓ
2
ℓ
ℓ
2
~ k2 =
+
.
(1)
(W (v, u)) − W (v, u)
kW (v, ·) − π
2m
4m2
u∈V

ℓ −W ℓ (v, u)| ≤ m−20 with probability
cu,v
By Lemma 3.3, we know that for every u ∈ V we have |W
2

d(u)
−20 .
1 − 1/m9 . Using W ℓ (v, u) ≤ 1, we have (W ℓ (v, u))2 − W ℓ (v, u) d(u)
2m + 4m2 − sv,u ≤ 3m
Combining this with Eq. (1), a union bound over all u ∈ V implies
P that with probability
~ k22 − u∈V sv,u ≤ 3m−19 . A
at least 1 − n · m−10 ≥ 1 − m−9 , we have that kW ℓ (v, ·) − π
union bound over all
with probability at least 1 − |S|/m−9 ≥ 1 − m−8 ,
P v ∈ S gives that
ℓ
2
−19
~ k2 − u∈V sv,u ≤ 3m .
kW (v, ·) − π

3.2. Completeness and Soundness

The proof of completeness is a straightforward application of the results from the previous
section.
Lemma 3.5 (Completeness). Let G(V, E) be a graph with conductance at least Φ. Then,
with probability at least 2/3, each vertex in G returns accept when it runs Algorithm 1.

7

→ p. 16

Proof. The probability that the algorithm rejects in Line 8 of Algorithm 1 is at most 1/10,
and we assume, for the remainder of the proof, that this event did not occur. If G has
2ℓ
~ k22 ≤ 1 − Φ2 /2 ≤
conductance at least Φ, then from Lemma 3.2 we know that kW ℓ (·, v) − π
exp(−Φ2 ℓ/2) ≤ m−20 for every vertex v. Lemma 3.4 implies that with probability at least
~ k22 − sv ≤ 3m−19 . Conditioning on this event, every vertex
9/10, it holds that kW ℓ (·, v) − π
accepts in line 12 of Algorithm 1.
To complete the analysis of the tester, we show that whenever the graph is ǫ-far from having
conductance Ω(Φ2 ), the tester rejects with probability at least 2/3. To this end, we actually
show that if the volume of weak vertices is small, then the graph can be converted to another
graph G′ by modifying at most ǫm edges such that the conductance is Ω(Φ2 ). The idea of the
analysis is due to Kale and Seshadhri [15], who analyzed a classic property tester for testing
expansion in graphs with vertex degrees bounded by a constant. We deviate from their analysis
where it becomes necessary to take care of arbitrary vertex degrees.
~ k2 > 6m−15 . The following lemma states
Let a vertex v ∈ V be called weak if kW ℓ (v, ·) − π
that if there exists a set of vertices S with small conductance, then there exists a set of weak
vertices T whose volume is at least a constant fraction of the volume of S. We defer the proof
of this technical lemma to the appendix.
Lemma 3.6. Let S ⊂ V be such that vol(S) ≤ vol(S̄) and cond(S) ≤ δ. Then, for any ℓ ∈ N
and any 0 < θ ≤ 1/10, there exists a set T ⊆ S such that vol(T ) ≥ θvol(S) and for every
1
2ℓ
~ k22 > 80m
v ∈ T , it holds that kW ℓ (v, ·) − π
7 (1 − 4δ) .
We can use Lemma 3.6 to separate weak vertices from the remaining graph.

Lemma 3.7. Let G = (V, E) be a graph. If the volume of weak vertices in G is at most
(1/100)ǫm, then there is a partition of V into P ∪ P̄ such that vol(P ) ≤ ǫm/10 and Φ(G[P̄ ]) ≥
Φ2 /256.
Proof. We partition the graph recursively into two sets (P, P̄ ). At the beginning, P0 = ∅
and P̄0 = V . As long as there is a cut (Ci , C̄i ) in P̄i−1 in step i with vol(Ci ) ≤ vol(C̄i )
and E(Ci , C̄i )/vol(Ci ) ≤ Φ2 /256, we set Pi = Pi−1 ∪ Ci and P̄i = V \ Pi . We continue this
until we don’t find such a cut or the condition vol(Pi+1P
) ≤ vol(P̄i+1 ) would be violated. The
number of edges going across the cut (P, P̄ ) is at most i |E(Ci , C̄i )|. Therefore, |E(P, P̄ )| ≤
Φ2
Φ2 P
i vol(Ci ) ≤ 256 vol(P ).
256
Now, assume that vol(P ) > (1/10)ǫm. Lemma 3.6 implies that there exists P ′ ⊆ P such that
1
~ k2 >
vol(P ) > ǫm/100 (where θ = 1/10) and for all v ∈ P ′ we have kW ℓ (v, ·) − π
vol(P ′ ) ≥ 10
1
1
2
2ℓ
′
(1 − 4Φ /256) > 80m10 . This means that P contains only weak vertices and has volume
80m7
at least ǫm/100, which contradicts our assumption that the volume of weak vertices in G
is at most ǫm/100. Therefore, vol(P ) ≤ ǫm/10 when the partitioning terminates. Hence
Φ(G[P̄ ]) ≥ Φ2 /256.
Finally, the following lemma states that few edge modifications in a graph with separated
weak vertices are sufficient to make it a graph with high conductance.
Lemma 3.8 ([17, Lemma 9]). Let G = (V, E) be a graph. If there exists a set P ⊆ V
such that vol(P ) ≤ ǫm/10 and the subgraph G[V \ P ] is a Φ′ -expander, then there exists an
algorithm that modifies at most ǫm edges to get a Φ′ /3-expander G′ = (V, E ′ ).
Combining the results on the separation of weak vertices and patching the graph (Lemmas 3.6
to 3.8) and approximating the endpoint distribution (Lemmas 3.3 and 3.4), we prove the

8

→ p. 17

soundness of the algorithm.
Lemma 3.9 (Soundness). Let G(V, E) be a graph. If G is ǫ-far from having conductance at
least Φ2 /768, then, with probability at least 2/3, each vertex in G returns reject when it runs
Algorithm 1.
Proof. First we note that if the volume of weak vertices is less than ǫm/100, then by Lemmas 3.7
and 3.8, the graph is ǫ-close to having conductance at least Φ2 /768. Therefore, the volume of
weak vertices is at least ǫm/100. Each vertex v is contained in S with probability Θ(d(v)/ǫm).
Hence, the expected number of weak vertices that are present in the sample S is at least 100.
Therefore, with probability at least 9/10, at least one weak vertex is sampled in S.
cℓ <
If W ℓ (v, u) < m−2 for some v ∈ S, u ∈ V , then with probability at least 9/10, W
v,u
−2
2m by Lemma 3.3. In this case, the algorithm will reject in line 15 of Algorithm 2. If
W ℓ (v, u) ≥ m−2 for all v ∈ S, u ∈ V , then with probability at least 9/10, it holds that
~ k2 − sv ≤ 3m−19 for every v ∈ S by Lemma 3.4. Since at least one vertex v ∈ S
kW ℓ (v, ·) − π
~ k2 > 6m−15 , the algorithm rejects in line 13 of Algorithm 1.
is weak, that is, kW ℓ (v, ·) − π

3.3. Unknown Size of the Graph
We describe how to get rid of the assumption that the size n of the graph G is known to the
tester if G is connected. Note that without any prior knowledge of G, no distributed tester
can distinguish between a graph with conductance Φ and two distinct copies of it (the latter
graph has conductance 0 and is ǫ-far from being a graph with conductance Φc for ǫ < Φc /2,
c ≥ 1).
First, we describe a slightly simpler version of the final algorithm. In the setting of the
simpler algorithm, we mark a single vertex that will initiate the test and will also give the final
answer of the tester. We call this vertex the maintainer (of the graph). The algorithm can be
easily adapted to the CONGEST model.
Let v ∈ V be a fixed vertex. The algorithm either makes n available at all vertices and
runs Algorithm 1 afterwards or v rejects because G does not have conductance Φ. If G has
conductance Φ, the algorithm never rejects.
We start with an initial set S = {v} that is grown in two phases. In the first phase, we
extend S to S ∪ Γ(S) as long as cond(S) ≥ Φ. In particular, v starts a BFS and in every
round, the vertices in the last level report their degree and the number of neighbors outside
of S to their parents. Similar to Algorithm 1, these are aggregated and sent to v along the
edges of the BFS tree. If cond(S) < Φ for the first time, the algorithm proceeds to the second
phase. It continues the BFS for − log(vol(S))/ log(1 − Φ) rounds and stops. If any vertex in
the graph notices a neighbor that is not in S after these rounds, then S 6= V and the algorithm
rejects. Otherwise, we have obtained the value of n = |S| that can be sent to all vertices, and
we continue by executing Algorithm 1.
Lemma 3.10. Let G = (V, E) be a graph and Φ ∈ [0, 1]. There is an algorithm that computes
n if G has conductance at least Φ. Otherwise, it either computes n or rejects. The round
complexity is O(log m/ log(1 − Φ)).
Proof. It is easy to see that if the algorithm explores the whole graph, it computes n correctly,
and else it rejects. Without loss of generality, let G have conductance Φ. Let Si be the set S
after i rounds and let S̄i = V \ Si . We denote the last round of the first (second) phase by k
(ℓ).

9

In the first phase, we have that vol(Si ) ≥ (1+Φ)·vol(Si−1 ) for every round i and by induction,
k ≤ log vol(Sk )/ log(1 + Φ) ≤ log m/ log(1 + Φ). We also have that vol(Sk ) ≥ m/2 ≥ vol(S̄k )
because G has conductance Φ. In the second phase, we have that vol(S̄i ) ≤ (1 − Φ) · vol(S̄i−1 )
for every round i. By induction, ℓ − k ≥ − log m/ log(1 − Φ) ≥ log vol(S̄k )−1 / log(1 − Φ)
implies that that vol(S̄ℓ ) = 0. Therefore, the algorithm has explored the whole graph. Clearly,
ℓ ∈ O(log m/ log(1 − Φ)).
To transform the algorithm into a tester in the CONGEST model, we start with each vertex
being a maintainer initially. In every round every vertex chooses the vertex with the smallest
id it has ever received a message from to be the maintainer and it forwards only this vertex’
messages (the latter maintains the congestion bound). At the end of the algorithm, if G has
conductance Φ, then there is only one maintainer (the vertex with the smallest id) and the
algorithm continues by executing Algorithm 1. Otherwise, there might be multiple vertices
that are still maintainers. However, none of these vertices has explored the whole graph, so all
of them send a broadcast message to reject.

4. Lower Bound
In this section, we prove a lower bound of Ω(log(n + m)) on the round complexity for testing
the conductance of a graph in the LOCAL model regardless of how the final decision of the
tester is derived from the single votes of the vertices.
For any v ∈ V , the k-disc of v, denoted by disck (G, v), is defined as the subgraph that is
induced by the vertices that are at distance at most k to v without the edges between vertices
at distance exactly k, and it is rooted at v. We refer to the isomorphism type of disck (G, v),
that is, the set of all rooted graphs isomorphic to disck (G, v), by disc∗k (G, v). Let girth(G)
denote the length of the shortest cycle in G. We need the following two lemmas to obtain the
distribution over graphs to prove the lower bound.
Lemma 4.1 ([20]; cf. [23, Section 16.8.3]). For every n′ ∈ N and every√d′ ∈ N there
exists a d-regular graph G of size n such that G has conductance Φ(G) = 1/ 2d and girth
2 log n/ log d, and n ≥ n′ , d ≥ d′ .

The second lemma states that we can sparsify an arbitrary cut E(V1 , V2 ) in a d-regular graph
with girth 3k without changing disc∗k (G, v) for any v ∈ V . In particular, it states that we can
remove two edges in the cut and add them somewhere else, or the cut has size poly(dk ) only.

Lemma 4.2 ([9, Lemma 8]). 2 Let G = (V, E) be a d-regular graph with girth(G) ≥
3k for k ≥ 2 and let V1 ∪˙ V2 = V be a partitioning of V . Then either there exists a
graph H = (V, F ) such that (i) girth(H) ≥ 3k, (ii) |F ∩ (V1 × V2 )| ≤ |E ∩ (V1 × V2 )| − 2,
and (iii) disc∗k (H, w) = disc∗k (G, w)∀w ∈ V , or E(V1 , V2 ) ≤ 6d3k .

To prove the lower bound, we use an auxiliary model we call the ISO-LOCAL model. In this
model, the input I(·) is empty but an additional oracle provides every vertex v with the ability
to construct disc∗r (G, v) in round r if it knows disc∗r−1 (G, ui ) of its neighbors u1 , . . . , ud(v) . It
should be noted that the ISO-LOCAL model is not a DCM due to the additional oracle.
Definition 4.3 (ISO-LOCAL model). Let DCM(G, pG , I) be a DCM instance such that I
maps the whole support to the empty string. In addition to sending and receiving messages,
2

The statement here is obtained as a special case by observing that we can assume L = 1 and λ = 0 in [9,
Lemma 8].

10

in every round r every vertex v is provided access to a function er,v : (N ∪ {⋆})r × (N ∪ {⋆})r →
{0, 1} during the local computation phase. The value of er,v ((i1 , . . . , ir′ ), (j1 , . . . , jr′′ )) is 1 iff
p′v (i1 , . . . , ir′ ) = p′v (j1 , . . . , jr′′ ), where
(
v
if ir = ⋆
p′v (i1 , . . . , ir ) :=
pp′v (⋆,i1 ,...,ir−1) (ir ) otherwise .
The instance DCM(G, pG , I) equipped with such an oracle is called ISO-LOCAL.



In other words, p′v (·) takes a path of length at most r that starts at v and that is defined by
a sequence of port numbers as input. Then, it maps the path to its endpoint in V . Finally,
er,v (·) tells whether two such paths end at the same vertex.
It is a basic observation that a distributed algorithm can only depend on information that
has reached it until the moment it performs the computation in question.
Lemma 4.4 (folklore; cf. [19, Section 2]). Let DNDA(A, O) be a DNDA. After r rounds,
the state of Av may depend only on d(v), I(v), the state of Au at time r − dist(v, u) for vertices
u with dist(v, u) < r and the random coins of A.

4.1. Proof of the Lower Bound
Let G = (V, E) be an expander graph obtained from applying Lemma 4.1 and let k = Θ(log n).
Observe that if a graph is d-regular and it has girth 3k, then all its k-discs are pairwise
isomorphic. In particular, all k-discs are full d-ary trees of depth k.
We will prove that a distributed algorithm DNDA(A, O) with round complexity r in the
ISO-LOCAL model decides based on the set of views disc∗r (G, v) that the different instances
of A have (see Lemma 4.5). Using Lemma 4.2, it will be easy to come up with a graph H that
is a bad expander but whose k-discs are isomorphic to the ones of G. This implies a lower
bound of k = Θ(log n) for testing conductance in the ISO-LOCAL model (see Proposition 4.6).
Finally, we prove (in the appendix) that a lower bound on the round complexity of a tester in
the ISO-LOCAL model implies the same bound in the LOCAL model. Actually, we prove the
contrapositive: a tester in the LOCAL model implies a tester in the ISO-LOCAL model (see
Proposition 4.7).
Lemma 4.5. Let DNDA(A, O) be a deterministic DNDA in the ISO-LOCAL model. The
output of Av depends only on disc∗r (G, v) and the port numbering (pv )v∈V .
Proof. Instead of analyzing DNDA(A, O), we will analyze a canonical algorithm DNDA(B, O)
that simulates DNDA(A, O) depending only on disc∗r (G, v). Employing B, we prove the following statement by induction: After the local computation phase of round r, the state of Av
depends only on disc∗r (G, v).
The first local computation phase of Av can only depend on the port numbering and I(v)
(the empty string). Therefore, Bv can simulate the execution of the first round of Av .
Let the current round be r > 1. Algorithm Bv maintains a rooted graph Hv that resembles
disc∗r (G, v). The adjacency lists of Hv are ordered according to (pv )v∈V . Let Hv (r) be the value
of Hv after the computation phase of round r. In the send phase, vertex v sends Hv (r) to each
of its neighbors. In the receive phase, vertex v receives graphs Hu1 (r), . . . , Hud(v) (r) from its
neighbors u1 , . . . , ud(v) . In the subsequent computation phase of round r + 1, vertex v extends
Hv (r) = disc∗r (G, v) to disc∗r+1 (G, v) = Hv (r + 1) by querying er,v on all pairs of vertices of

11

V (Hv (r)) ∪ V (Hu1 (r)) ∪ . . . ∪ V (Hud(v) (r)) to identity vertices and patching the different views
together.
Note that Hv (r + 1) also provides the isomorphism type of disc∗r−dist(v,u) (G, u) for every
vertex u at distance at most r from v. Since the adjacency lists of Hv are ordered according
to the port numbering, it is also possible to reconstruct er−dist(v,u),u (·). By the induction
hypothesis, Bv can now simulate round r − dist(v, u) of Au for every such u. By Lemma 4.4,
this is enough to simulate the local computation phase of round r of Au .
We use the lemma to show that there is no tester for conductance in the ISO-LOCAL model.
Proposition 4.6. Let G = (V, E) be a graph on n vertices, and let Φ > 0 be any constant.
Any algorithm for testing if G has conductance at least Φ or is ǫ-far from having conductance
at least cΦ2 (for a constant c) in the ISO-LOCAL model that succeeds with probability 2/3
requires Ω(log n) rounds of communication.
 2

Proof. Let G = (V, E) be a d-regular graph provided by Lemma 4.1 and set k = 31 logd cΦ6−ǫ dn .
Without loss of generality assume that n is even, and let S ⊂ V be a set of size n/2. Apply
Lemma 4.2 (with V1 = S and V2 = V \ S) repeatedly to G until |E(S, V \ S)| ≤ 6d3k holds.
Let H = (V, E ′ ) be the resulting graph. We have that |E ′ (S, V \ S)| ≤ (cΦ2 − ǫ)dn, and
vol(S) = nd/2. Therefore, H is ǫ-far from having conductance cΦ2 . Let DG (DH ) be the
uniform distribution over all ISO-LOCAL models DCM(G, pG , I) (DCM(H, pH , I)) such that
pG (pH ) ranges over all possible mappings, that is, port numberings.
We use Yao’s principle to prove the lower bound. Let DNDA(A, O) be a tester for conductance that has round complexity smaller than k in the ISO-LOCAL model. Since G is
d-regular and girth(G) ≥ 3k, disc∗k (G, v) is a full d-ary tree of depth k for every v ∈ V . For any
pair u, v ∈ V , we have that disc∗k (G, u) is equal to disc∗k (H, v) by Lemma 4.2. Since the port
numberings of two vertices are independent of each other, (pv )v∈V is a valid port numbering for
G ∈ DG iff it is valid for H ∈ DH . By Lemma 4.5, DNDA(A, O) cannot distinguish between
G and H.
To complete the proof of the lower bound, we show (in the appendix) that each vertex in
the graph in the ISO-LOCAL model can choose an id randomly, and with high probability no
two ids will be identical.
Proposition 4.7. Let DNDA(A, O) be a randomized tester in the LOCAL model that succeeds
with probability p. Then, there is a randomized tester DNDA(B, O) in the ISO-LOCAL model
that succeeds with probability at least p − o(1), and has the same round complexity.

5. Open Problems
In the case of one-sided distributed testers, it is natural to define the acceptance rule O(·) of
a distributed tester such that all vertices have to accept or at least one vertex has to reject.
This is because in the case of rejection, the tester is required to observe a witness. However,
for two-sided testers no such requirement exists. Requiring that all vertices either accept or
reject simultaneously, which can be satisfied by a slightly modified version of Algorithm 1,
seems to be quite strong. On the other hand, it might not always be possible to obtain a lower
bound that is independent of the acceptance rule as in Theorem 1.2. To this end, it would be
interesting to compare the power of different rules.

12

→ p. 21

Acknowledgments
We would like to thank Gopal Pandurangan for pointing out related work [7, 21], and we would
like to thank Pan Peng for inspiring discussions on spectral graph theory. We are grateful for
the helpful comments of anonymous reviewers.

13

References
[1] Zvika Brakerski and Boaz Patt-Shamir. Distributed discovery of large near-cliques. Distributed Computing, 24(2), 2011. doi: 10.1007/s00446-011-0132-x.
[2] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev. Fast distributed algorithms for testing graph properties. In Proceedings of the 30th International
Symposium on Distributed Computing (DISC), 2016.
[3] Fan R. K. Chung. Diameters and eigenvalues. Journal of the American Mathematical
Society, 2(2), 1989.
[4] Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997. ISBN
978-0-8218-8936-7.
[5] Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree graphs. In
Proccedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS),
2007.
[6] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In
Proccedings of the 47th ACM Symposium on Theory of Computing (STOC), 2015.
[7] Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Distributed random walks. Journal of the ACM (JACM), 60(1), 2013.
[8] Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro
Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three
Notes on Distributed Property Testing. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), to appear, 2017.
[9] Hendrik Fichtenberger, Pan Peng, and Christian Sohler. On constant-size graphs that
preserve the local structure of high-girth graphs. In Proccedings of the 19th International
Workshop on Randomization and Computation (RANDOM), 2015.
[10] Pierre Fraigniaud, Ivan Rapaport, Ville Salo, and Ioan Todinca. Distributed testing of
excluded subgraphs. In Proceedings of the 30th International Symposium on Distributed
Computing (DISC), 2016.
[11] Oded Goldreich. Introduction to testing graph properties. In Property Testing. Springer,
2010.
[12] Oded Goldreich.
Introduction to Property Testing.
Cambridge
versity Press,
2017,
to appear.
ISBN 978-1107194052.
http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html.

UniURL

[13] Oded Goldreich and Dana Ron. On Testing Expansion in Bounded-Degree Graphs. Electronic Colloquium on Computational Complexity (ECCC), 2000.
[14] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property Testing and Its Connection
to Learning and Approximation. Journal of the ACM (JACM), 45(4), 1998. doi: 10.1145/
285055.285060.

14

[15] Satyen Kale and C. Seshadhri. An expansion tester for bounded degree graphs. SIAM
Journal on Computing (SICOMP), 40(3), 2011. doi: 10.1137/100802980.
[16] David Asher Levin, Y. Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times.
American Mathematical Society, 2009. ISBN 978-0-8218-4739-8.
[17] Angsheng Li and Pan Peng. Testing Small Set Expansion in General Graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science
(STACS), volume 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. ISBN
978-3-939897-78-1.
[18] Angsheng Li, Yicheng Pan, and Pan Peng. Testing Conductance in General Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 18(101), 2011.
[19] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing
(SICOMP), 21(1), 1992. doi: 10.1137/0221015.
[20] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3), 1988. doi: 10.1007/BF02126799.
[21] Anisur Rahaman Molla and Gopal Pandurangan. Distributed Computation of Mixing
Time. In Proceedings of the 18th International Conference on Distributed Computing and
Networking (ICDCN). ACM, 2017. ISBN 978-1-4503-4839-3.
[22] Asaf Nachmias and Asaf Shapira. Testing the expansion of a graph. Information and
Computation, 208(4), 2010. doi: 10.1016/j.ic.2009.09.002.
[23] Uwe Naumann and Olaf Schenk, editors. Combinatorial Scientific Computing. CRC Press,
2012. ISBN 978-1-4398-2735-2.
[24] Alistair Sinclair. Algorithms for Random Generation and Counting: A Markov Chain
Approach. Birkhauser Verlag, 1993. ISBN 978-0-8176-3658-6.

15

A. Proofs from Section 3
A.1. Algorithms 3 and 4
Algorithm 3 Construct BFS tree
1: procedure BFS(G, D)
2:
let every vertex v do
3:
Tv ← (v, ·)
4:
minid ← v
5:
send (v, v) to every neighbor u ∈ Γ(v)
6:
for D rounds, let every vertex w do
7:
Rv ← {(v ′ , u′ ) received | u′ ∈ Γ(w)}
8:
(v, u) ← arg min(v′ ,u′ )∈Rv v ′
9:
if Tw = (·) or v ′ < minid then
10:
Tw ← (v, u)
11:
send (v, w) to all neighbors 6= u

⊲ Set root to itself, parent to empty

⊲ Set root to v, parent to u

Algorithm 4 Aggregate sum of vertex values and propagate it to all vertices
Require: ∀v : v has local information
f (v)
P
Ensure: ∀v : v has information
u∈V f (u)
1: procedure AggregateSum(G, D, f : V → R)
2:
for D rounds, let every vertex v do
3:
if v received partial
P sums su from all its children u in BFS tree then
4:
sv ← f (v) + u su
5:
send sv to parent in BFS tree
6:
let vertex root r of BFSPtree do
7:
send total sum s = v f (v) to all children
8:
for D rounds, let every vertex v do
9:
if v received total sum s from its parent then
10:
send sv to all children in BFS tree
11:
return sv
⊲ consider sv to be the output of the algorithm

A.2. Proof of Lemma 3.3
Lemma 3.3. Consider Algorithm 2. For every v, u ∈ V , it holds with probability at least
ℓ −W ℓ (v, u)| ≤ m−20 and, conditioned on the previous, (ii) if W
ℓ < m−2
cv,u
cv,u
1−m−10 that (i) |W
then G has conductance less than Φ.
c ℓ ] = W ℓ (v, u). By Hoeffding’s inequality, it holds that
Proof. We have E[W
v,u


N
ℓ
ℓ
−10
cv,u − E[W
cv,u ]| ≥ m ] ≤ 2 exp −
≤ m−10 .
Pr[|W
3m40

(2)

c ℓ ]| < m−20 , which happens with probability at least 1 − 1/m10 .
c ℓ − E[W
Condition on |W
v,u
v,u
c ℓ < m−2 , then
If W
v,u
ℓ
ℓ
cv,u
cv,u
W ℓ (v, u) = E[W
]<W
+ m−20 = m−2 + m−10 < 2m−2 .

16

~ k2 from below.
Let π ′ = 1v . We bound kW ℓ π~′ − π
~ k2 ≥ |W ℓ (v, u) − d(u)/2m| ≥ −(2m−2 − 1/(2m)) ≥ 1/(4m) .
kW ℓ π~′ − π
By the contrapositive of Lemma 3.2, G has conductance less than Φ.

A.3. Proof of Lemma 3.6
The (normalized) Laplacian becomes useful when studying cuts in a graph.
Definition A.1 (Normalized Laplacian). Let G = (V, E) be a graph. The normalized
Laplacian is defined by L := I − D −1/2 AD −1/2 .

The following decomposition of the walk matrix turns out to be useful in this context.

Lemma A.2 ([16, Lemma 12.2]). 3 Let G be a graph. The walk matrix W can be decomposed
as
n
X
f~i (u)f~i (v)
W ℓ (u, v)
µℓi p
=1+
.
~ (v)
π
d(u)d(v)
i=2

We would like to prove that if the conductance of some set S of vertices is small, then a
constant fraction of the volume of S belongs to some (basically) weak vertices. The following
statement is a preliminary version of the result that we aim for. It proves the existence of a
single vertex with some (unknown) volume only.

Lemma A.3. Let S ⊂ V be such that vol(S) ≤ vol(S̄) and cond(S) ≤ δ. Then, for any ℓ ∈ N,
there exists a vertex v ∈ S such that
~ k22 >
kW ℓ (v, ·) − π

1
(1 − 4δ)2ℓ
16m7

P
~ k22 > (1 − 4δ)2ℓ /(16m7 ) and apply an averaging
Proof. We will argue that 1s x∈S kW ℓ (x, ·) − π
argument to conclude.
Assume for the moment that
!2
n
Xp
X
vol(S)
, where τ = (1 − 4δ).
(3)
d(x)f~i (x)
≥
4
i≥2
µi >τ

3

x∈S

In [16], the result is stated for a right stochastic walk matrix
and its right eigenbasis that is orthonormal with
P
respect to the non-standard inner product hf, giπ =
f (x)g(x)~
π (x). The statement here is adapted to our
notation.

17

Then, the following calculation concludes the proof:
1X
~ k22
kW ℓ (x, ·) − π
s
x∈S

=


1X D 
2mD −1 W ℓ (x, ·) − ~1
s
2m

2
2

x∈S

2

n
X
f~i (x) −1/2 ~
1 X
µℓi p
D
= 2
D
fi
4m s
d(x)
x∈S

i≥2

X D 1/2
1
≥ 2
4m n
s · d(x)
x∈S

≥

1
τ 2ℓ
4m2 n3 s2

≥

4m2 n3 s2

1

τ 2ℓ

, by Lemma A.2

n
X

i≥2
µi >τ

n
X

p
ℓ

µi

i≥2

Xp

2
2

d(x)f~i (x)f~i
!2

d(x)f~i (x)

x∈S

, by Jensen’s inequality
2

kf~i k22

vol(S)
, by Eq. (3)
4

1
(1 − 4δ)2ℓ , w.l.o.g. vol(S) ≥ 1 .
16m7
The remaining calculation is similar
to the
E proof of [15, Lemma 3.5]. We prove Eq. (3).
D
1/2
1/2
~
~ in the orthonormal eigenbasis
~ = D ~1S . Denote αi := D ~1S , fi . Representing u
Let u
{f~i }i∈[n] of N , we have
n
X
~ =
αi f~i .
u
≥

i=1

By the definition of the normalized Laplacian,

~ T L~
~ T Iu
~ −u
~T Nu
~.
u
u=u

(4)

Observe that
T

~ Iu
~ =
u
k~
uk22 =

k~
uk22

Xp

=

n
X

α2i

(5)

i

2

d(i) = vol(S) .

(6)

i∈S

The second term of the right-hand side of Eq. (4) is equal to
!
! n
!
!
n
n
n
X
X
X
X
~T Nu
~ =
αi µi f~i
αi f~iT
αi f~i =
αi f~iT N
u
i=1

i=1



i=1

i=1







n
n
X
 X

2
T ~
~


=
αi µi fi fj  + 
α2i µi f~iT f~j 


=

i,j=1
i=j
n
X
α2i µi
i=1

18

i,j=1
i6=j

+ 0.

(7)

Combining Eqs. (4), (5) and (7), we get that
~ T L~
~ T Iu
~ −u
~T Nu
~ = k~
u
u=u
uk22 −

n
X

α2i µi .

(8)

i=1

On the other hand,
X

T

~ L~
u
u=

(i,j)∈E

!2

~ (j)
~ (i)
u
u
p
−p
d(i)
d(j)

Equations (6), (8) and (9) imply
X

i∈[n]

=

X

(1 − 0) ≤ δvol(S) .

(9)

(i,j)∈E(S,S̄)

α2i µi ≥ (1 − δ)vol(S) .

(10)

P
Let H be the eigenvalues µi > 1 − 4δ, and define x := µ∈H α2i . Rewriting Eq. (10), we get
that


X
α2i − x (1 − 4δ) ≥ (1 − δ)vol(S)
x+
i∈[n]

⇔

4δx + vol(S)(1 − 4δ)

⇔

x

≥ (1 − δ)vol(S), by Eq. (5)
3vol(S)
≥
4

(11)

Note that
D

α1 = D

1/2~

√

1S , 2m

−1

D

Therefore, we have that
n
X

i≥2
µi >τ

Xp

x∈S

E

1 X
vol(S)
=
1 =√
d(i) ≤ p
2m i∈S
2vol(S)

1/2~

!2

d(x)f~i (x)

= x − α21 ≥

vol(S)
.
4

r

vol(S)
.
2

(12)

Actually, our goal is to get a result that is a bit stronger than Lemma A.3. However, it
follows from Lemma A.3 as [15, Lemma 3.6] follows from [15, Lemma 3.5]. It states that even
if we exclude some vertices that account for a small fraction of the total volume of S, there
exists a basically weak vertex.
Lemma A.4. Let T ⊆ S ⊂ V be such that vol(S) ≤ vol(S̄), cond(S) ≤ δ and vol(T ) =
(1 − θ)vol(S) for some 0 < θ ≤ 1/10. Then, for any ℓ ∈ N, there exists a vertex v ∈ T such
that
1
~ k22 >
(1 − 4δ)2ℓ
kW ℓ (v, ·) − π
80m7

19

~ S := D 1/2~1S and u
~ T := D 1/2~1T . Let αi := h~
Proof. Let u
uS , f~i i and βi := h~
uT , f~i i. Equation (11) holds, where H = {µi | µi > (1 − 4δ)}:
X

α2i >

i∈H

3vol(S)
.
4

It holds that
X
X
X
X
~ T k22 =
(αi − βi )2 ≤
(αi − βi )2 = k~
uS − u
d(x) −
d(x) = vol(S) − vol(T ) = θvol(S) .
i∈H

i

x∈S

x∈T

Using the triangle inequality ka − bk2 ≥ kak2 − kbk2 on the subspace spanned by the basis H,
we have

 2 "r
#2
sX
sX
X
p
3vol(S)
βi2 ≥ 
− θvol(S)
α2i −
(αi − βi )2  >
4
i∈H
i∈H
i∈H
r
3θ
3vol(S)
−
vol(S) + θvol(S)
=
4
4
11
> vol(S)
20
Observe that β12 ≥ α21 ≥

vol(S)
2 .

n
X

i≥2
µi >τ

Similar to Eq. (10), we have

Xp

x∈T

!2

d(x)f~i (x)

=

X

i∈H

βi2 − β12 ≥

vol(S)
.
20

Therefore, we obtain that
vol(S)
1X
~ k22 ≥
kW ℓ (x, ·) − π
(1 − 4δ)2ℓ .
s
80m2 n3 s2
x∈T

Lemma 3.6. Let S ⊂ V be such that vol(S) ≤ vol(S̄) and cond(S) ≤ δ. Then, for any ℓ ∈ N
and any 0 < θ ≤ 1/10, there exists a set T ⊆ S such that vol(T ) ≥ θvol(S) and for every
1
2ℓ
~ k22 > 80m
v ∈ T , it holds that kW ℓ (v, ·) − π
7 (1 − 4δ) .
Proof. Apply Lemma A.4, mark the weak vertex that has been found in T and exchange it
for some vertex in S \ T that has not been marked yet. By Lemma A.4, we can repeat this
process until vol(T ) ≥ θvol(S).
We sketch a proof here. The algorithm is as described in Section 3.3.

20

B. Proofs from Section 4
B.1. Proof of Proposition 4.7
Proposition 4.7. Let DNDA(A, O) be a randomized tester in the LOCAL model that succeeds
with probability p. Then, there is a randomized tester DNDA(B, O) in the ISO-LOCAL model
that succeeds with probability at least p − o(1), and has the same round complexity.
Proof. We make a simple modification to A to obtain B: In the first local computation phase,
Bv draws a random number idv uniformly from {1, . . . , n3 } and feeds it into Av as I(v). Then,
Av is executed as normal. For u, v ∈ V , the probability that idu and idv are equal is 1/n3 .
Applying a union bound, with probability 1 − o(1), it holds that idu 6= idv for every u, v ∈ V .
We then run algorithm A on this new instance and output the result.

21

