# A Distributed Conductance Tester Without Global Information Collection

Tuğkan Batu Department of Mathematics, London School of Economics and
Political Science, UK. Email<EMAIL_ADDRESS>Chhaya Trehan Department of
Mathematics, London School of Economics and Political Science, UK and
Department of Computer Science, University of Bristol, UK. Email:
<EMAIL_ADDRESS>
(May 23, 2023)

Given an undirected graph $G$ and a conductance parameter $\alpha$, the
problem of testing whether $G$ has conductance at least $\alpha$ or is far
from having conductance at least $\Omega(\alpha^{2})$ has been extensively
studied (see [17, 6, 18, 22]) for bounded degree graphs in the classic
property testing model.

In the last few years, the same problem has also been addressed in non-
sequential models of computing such as MPC and distributed CONGEST. However,
all the algorithms in these models like their classic counterparts apply an
aggregate function over some statistics pertaining to a set of random walks on
$G$ as a test criteria. The only distributed CONGEST algorithm for the problem
by [10] tests conductance of the underlying network in the unbounded degree
graph model. Their algorithm builds a rooted spanning tree of the underlying
network to collect information at the root and then applies an aggregate
function to this information. We ask the question whether the parallelism
offered by distributed computing can be exploited to avoid information
collection and answer it in affirmative. We propose a new algorithm which also
performs a set of random walks on $G$ but does not collect any statistic at a
central node. In fact, we show that for an appropriate statistic, each node
has sufficient information to decide on its own whether to accept or not.
Given an $n$-vertex, $m$-edge undirected, unweighted graph $G$, a conductance
parameter $\alpha$, and a distance parameter $\epsilon$, our distributed
conductance tester accepts $G$ if $G$ has conductance at least $\alpha$ and
rejects $G$ if $G$ is $\epsilon$-far from having conductance
$\Omega(\alpha^{2})$ and does so in $O(\log n)$ rounds of communication.
Unlike the algorithm of [10], our algorithm does not rely on the wasteful
construction of a spanning tree and information accumulation at its root. This
makes our algorithm time and communication efficient and avoids a central
point of failure.

##  1 Introduction

Many distributed algorithms are known to perform better provided that the
underlying distributed network satisfies a certain property. For example, the
randomised leader election algorithm by [19] works better on graphs that are
good expanders. Similarly, [24] present fast distributed coloring algorithms
for triangle-free graphs. Therefore, it makes sense to check if the graph of
the underlying network satisfies a certain property or not. However, it may be
hard to efficiently _verify_ certain global graph properties in the CONGEST
model of distributed computing. In this model, each vertex of the input graph
acts as a processing unit and works in conjunction with other vertices to
solve a computational problem. The computation proceeds in synchronous rounds,
in each of which every vertex can send an $O(\log n)$-bits message to each of
its neighbours, do some local computations and receive messages from its
neighbours. (See [23] for more details.)

_Distributed decision_ problems are tasks in which the vertices of the
underlying network have to collectively decide whether the network satisfies a
global property $\mathcal{P}$ or not. If the network indeed satisfies the
property, then all vertices must accept and, if not, then at least one vertex
in the network must reject. For many global properties, lower bounds on the
number of rounds of computation of the form $\tilde{\Omega}(\sqrt{n}+D)$ are
known for distributed decision, where $n$ is the number of vertices and $D$ is
the diameter of the network. (See [7] for more details.) It makes sense to
relax the decision question and settle for an approximate answer in these
scenarios as is done in the field of property testing (see [13, 16]) in the
sequential setting.

A property testing algorithm in the sequential setting arrives at an
approximate decision about a certain property of the input by _querying_ only
a small portion of it. Specifically, an $\epsilon$-tester for a graph property
$\mathcal{P}$ is a randomised algorithm that can distinguish between graphs
that satisfy $\mathcal{P}$ and the graphs that are $\epsilon$-far from
satisfying $\mathcal{P}$ with high constant probability. An $m$-edge graph $G$
is considered $\epsilon$-far from satisfying $\mathcal{P}$ if one has to
modify (add or delete) more than $\epsilon\cdot m$ edges of $G$ for it to
satisfy $\mathcal{P}$. Two-sided error testers may err on all graphs, while
one-sided error testers have to present a witness when rejecting a graph. The
cost of the algorithm is measured in the number of queries made. (See [13, 16,
15, 14] for a detailed exposition of the subject.)

###  1.1 Distributed Property Testing

A _distributed property testing_ problem is a relaxed variant of the
corresponding distributed decision problem, where if the input network
satisfies a property, then, with high constant probability, all the vertices
must accept and, if the input network is $\epsilon$-far from satisfying the
property, then at least one vertex must reject. The definition of "farness" in
distributed setting remains the same as in the classical setting. The
complexity measures are the number of rounds required to test the property and
the number of messages exchanged during the execution of the tester.
Distributed property testing has been an active area of research recently. The
work of [3] was the first to present a distributed algorithm (for finding
near-cliques) with a property testing flavour. Later, Censor-Hillel, Fischer,
Schwartzman and Vasudev [4] did a more detailed study of distributed property
testing. There has been further study on the topic (see [9] and [11]) in the
specific context of subgraph freeness.

###  1.2 Conductance Testing

We address the problem of testing the conductance of an unweighted, undirected
graph $G=(V,E)$ in the distributed CONGEST model of computing. Throughout, we
denote $|V|$ by $n$ and $|E|$ by $m$. A distributed conductance tester can be
a useful pre-processing step for some distributed algorithms (such as [19])
which perform better on graphs with high conductance. Given a graph $G=(V,E)$,
and a set $A\subseteq V$, the _volume_ of $A$ (denoted
$\operatorname{vol}(A)$) is the sum of degrees of vertices in $A$. We say that
a graph $G=(V,E)$ is an _$\alpha$ –conductor_ if every $U\subseteq V$ such
that $\operatorname{vol}(U)\leq\operatorname{vol}(V)/2$ has conductance at
least $\alpha$. Here, the conductance of a set $A$ is defined as
$\frac{E(A,V\setminus A)}{\operatorname{vol}(A)}$, where $E(A,V\setminus A)$
is the number of edges crossing between $A$ and $V\setminus A$. A closely
related property of graphs is their expansion. We call a graph $G=(V,E)$ an
_$\alpha$ –vertex expander_ if every $U\subseteq V$ such that $|U|\leq|V|/2$
has at least $\alpha|U|$ neighbours. Here a vertex $v\in V\setminus U$ is a
neighbour of $U$ if it has at least one edge incident to some $u\in U$.
Similarly, $G$ is called an _$\alpha$ –edge expander_, if every $U\subseteq V$
such that $|U|\leq|V|/2$ has at least $\alpha|U|$ edges crossing between $U$
and $V\setminus U$.

For a constant $d$, A graph $G=(V,E)$ is called a _bounded-degree graph_ with
degree bound $d$ if every $v\in V$ has degree at most $d$. In this case, both
the vertex and edge expansions are bounded by a constant times (depending on
$d$) the conductance. Testing expansion (essentially testing conductance) in
bounded degree model has been studied for a long time in the classic property
testing model. In this setting, the problem of testing expansion was first
studied by [17] and later by [6]. Their work was followed by the state of the
art results by [18] and [22]. Both these papers present
$\tilde{O}(\sqrt{n}/\alpha^{2})$-query testers for distinguishing between
graphs that have expansion at least $\alpha$ and graphs that are
$\epsilon$-far from having expansion at least $\Omega(\alpha^{2})$. In the
last few years, the same problem has also been addressed in non-sequential
models of computing such as MPC [21] and distributed CONGEST [10]. The
distributed algorithm by Fichtenberger and Vasudev [10] tests the conductance
of the input network in the unbounded-degree graph model.

A typical algorithm for the problem in the sequential, as well as non-
sequential, models can be thought of as running in two _phases_. In the first
phase, the algorithm performs a certain number of short ($O(\log n)$-length)
random walks from a randomly chosen starting vertex. The walks should mix well
on a graph with high conductance and should take longer to mix on a graph
which is far from having high conductance (at least from some fraction of
starting vertices). In the second phase, the algorithm then checks whether
those walks mixed well or not. For that, the algorithm gleans some information
from every vertex in the graph and computes some aggregate function.
Specifically in the classic and MPC settings, the algorithms count the total
number of pairwise collisions between the endpoints of the walks. The only
known distributed algorithm for the problem by Fichtenberger and Vasudev [10]
precedes the first phase by building a rooted BFS spanning tree of the input
graph.111If the construction of BFS tree takes longer than $O(\log n)$ rounds
the algorithm rejects without proceeding to the first phase since all good
expanders have small diameter. However, a bad expander such as a dumbbell
graph may also have small diameter, so their algorithm still need to proceed
with the test after the successful construction of the spanning tree. This
spanning tree is used for collecting information from the endpoints of the
random walks in the second phase. Specifically, their algorithm estimates the
discrepancy of the endpoint probability distribution from the stationary
distribution by collecting the estimate of discrepancy on each endpoint at a
central point. If the overall discrepancy is above a certain threshold, the
algorithm rejects the graph. This process of building a spanning tree and
collecting information at the root to decide if the property holds or not
takes a global and centralized view of the testing process.

The following natural question arises in the context of the second phase:

######  Question 1.

Is it possible to execute the second phase without computing a global
aggregate function?

In the classic setting, one strives for testers that make a sublinear (in $n$
or $m$) number of queries which translates to running a sublinear number of
walks. With only a sublinear $(O(\sqrt{n}))$ number of walks, one hardly
expects to see any useful information by itself on any individual vertex or in
a small constant neighbourhood around it to know if the walks mixed well or
not. Therefore, one has to rely on an aggregate function such as the total
number of pairwise collisions between the endpoints of the walks.

In the non-sequential settings such as distributed CONGEST, one can utilise
the parallelism to run a superlinear number of short walks while keeping the
run time proportional to the length of the walks. This inspires us to stick to
Question 1 in distributed setting and investigate what information one should
store at each vertex during phase $1$ and how it should be processed _locally_
in phase $2$ to allow each node to decide locally whether it is part of a good
conductor or not. This leads us to answer the following question in
affirmative for general graphs (with no degree bound), provided all the nodes
know $n$ and $m$ beforehand:

######  Question 2.

Can we test the conductance in distributed CONGEST model without relying on
any global information collection at a central point?

Savings in communication and round complexity. The advantage of not having to
collect global information is that it lets us do away with the wasteful
construction of a spanning tree and information accumulation at the root. Note
that we do not need to do any pre-processing for the construction of the
spanning tree before phase $1$. In contrast, the algorithm of Fichtenberger
and Vasudev [10], performs $O(\log n)$ rounds of communication and exchange
exactly $m$ messages in each of these rounds during pre-processing. During
phase $1$, our algorithm and that of [10] have same round and message
complexity. After phase $1$, each node in our algorithm can compute its output
bit without any information exchange. In contrast the algorithm of [10]
performs an information gathering step for collecting some statistics of the
random walks from their endpoints to to the root of the spaning tree. This
saves us $O(\log n)$ rounds of communication and $O(n)$ messages (required for
convergecast back to the root) in phase $2$. All these savings make our
algorithm more time and communication efficient.

More importantly, our algorithm avoids a central point of failure.
Additionally, our algorithm can tolerate any number of edge deletions during
phase $2$. Any implementation of parallel random walks in dynamic networks
(with edge deletions) during phase $1$ opens up the possibility of a fully-
fault-tolerant tester for dynamic networks.

Finally, we believe that our approach to distributed property testing for
conductance with emphasis on avoiding global information collection provides a
new perspective for distributed property testing in general.

###  1.3 The Main Result

We study the problem of testing the conductance of undirected graphs in the
CONGEST model. We present a two-sided error distributed CONGEST algorithm for
testing the conductance.

######  Theorem 3.

For an input graph $G=(V,E)$, and parameters $0<\alpha<1$ and $\epsilon>0$,
there exists an $O(\log n/\alpha^{2})$-round distributed algorithm for testing
with high constant probability whether $G$ is an $\alpha$-conductor or is
$\epsilon$-far from being an $\Omega(\alpha^{2})$-conductor.

###  1.4 Technical Overview

In this section, we give a general overview of our algorithm and the concepts
used in arriving at our algorithm. Like all the previous algorithms for
conductance testing, our algorithm proceeds in two phases. In the first phase,
we perform a certain number of random walks from a randomly selected starting
vertex. To boost the success probability of the process, we repeat this
process in parallel from a constant number of randomly selected starting
vertices. The main technical challenge in running random walks in parallel
from different starting vertices is the congestion on the edges. As done by
[10], we overcome this problem by not sending the entire trace of the walk
from its current endpoint to the next. For each starting point $q$ and for all
the walks going from $u$ to $v$, we simply send the ID of $q$ and the number
of walks destined for $v$ to $v$. At the end of this process, for each
starting point $q$, we simply store at each vertex $v$, the number of walks
that ended at $v$. In phase $2$, each vertex $v\in V$ looks at the information
stored at $v$ at the end of phase $1$ to check if the number of walks received
from any starting vertex is more than a certain threshold. If so, it outputs
_Reject_ and, otherwise, it outputs _Accept_.

To show that the number of walks received by a vertex $v$ is sufficient to
decide whether $v$ is part of a good conductor or not, we proceed as follows.
A technical lemma from [20] implies that if a graph $G$ is $\epsilon$-far from
being an $\alpha$-conductor, then there exists a set $S\in V$ of sufficiently
low conductance (of cut $(S,V\setminus S)$, see Definition 4)) and
sufficiently high volume. It follows intuitively that it is likely that a
short random walk starting from a randomly selected starting vertex in $S$
should not go very far and end in $S$. In particular, we show that there exist
a subset $P\subseteq S$ such that short walks starting from any $v\in P$ end
in a large enough region $T$ (subset of $S$) around $v$. We make this notion
precise by using spectral graph theory to show that a large portion of the
volume of low-conductance set $S$ (as described above) belongs to _sticky_
vertices. We call a vertex $v\in S$ sticky if there exists a set $T\subseteq
S$ such that $v\in T$ and short random walks starting from $v$ end in $T$ with
a _sufficiently_ high probability. We define $\operatorname{trap}(v,T,\ell)$
as the probability that an $\ell$ length walk starting from $v\in T\subseteq
S$ ends in $T$.

Observe that our definition of trap probability is slightly different from the
one generally used in the analysis of similar problems. The notion of trap
probability is generally used to bound the probability of an $\ell$-step
random walk staying in a specific set for its entire duration (in each of the
$\ell$ steps). See for example the definitions of _remain_ and _escape_
probabilities in [12]. Similarly, Czumaj and Sohler also implicitly use the
concept of trap probability in their expansion tester [6] and they also bound
the probability of a walk staying inside a set of low conductance for its
entire duration. We relax the definition a bit and only care about the walk
_ending_ in a subset of a low conductance set. This allows us to also use the
walks that may have briefly escaped the low conductance region when counting
the number of trapped walks. Thus, if we run sufficiently many walks from one
of the sticky vertices, then a lot of them will end in a subset $T$ of $S$ and
some vertex in $T$ will see a lot more walks than any vertex in a good
conductor should. To ensure that we pick one of the sticky vertices as a
starting vertex, we sample each vertex to be a starting vertex with
appropriate probability.

###  1.5 Organisation

The rest of the paper is organised as follows. In Section 2, we provide
necessary definitions and state some basic lemmas that are used in rest of the
paper. In Section 3, we provide the pseudocode and a detailed description of
our testing algorithm. Section 3.1 is dedicated to the proof of our main
theorem.

##  2 Preliminaries

Let $G=(V,E)$ be an unweighted, undirected graph on $n$ vertices and $m$ edges
with no self-loops and multiple edges. We assume that the vertices of $G$ have
unique identifiers from the set $\\{1,2,\ldots,n\\}$. Each vertex $v\in V$ is
a processing unit and can communicate with its _neighbours_ , $N(v)$, using
their identifiers. For a given vertex $v\in V$, $\operatorname{deg}(v)$
denotes the _degree_ of $v$.

A graph $G$ is said to be _$\epsilon$ -far_ from satisfying a graph property
$\mathcal{P}$ (or, in other words, being a member of a certain family of
graphs closed under graph isomorphism), if one needs to add and/or delete more
than $\epsilon m$ edges to $G$ in order to turn it into a graph satisfying
$\mathcal{P}$.

For sets $A,B\subseteq V$, we denote by $E(A,B)$ the number of edges that have
one endpoint in $A$ and the other endpoint in $B$.

A cut in a graph is a partition of the vertices of the graph into two disjoint
subsets. Given a graph $G=(V,E)$ any subset $S\subseteq V$ defines a cut
denoted by $(S,\overline{S})$, where $\overline{S}=V\setminus S$.

######  Definition 4.

Given a cut $(S,\overline{S})$ in $G$, the conductance of $(S,\overline{S})$
is defined as

$\frac{E(S,\overline{S})}{\min\\{\operatorname{vol}(S),\operatorname{vol}(\overline{S})\\}},$

where $\operatorname{vol}(A)=\sum_{v\in A}\operatorname{deg}(v)$.
Alternatively, we also refer to the conductance of a cut $(S,\overline{S})$ as
the _conductance of set $S$_. The conductance of a graph is the minimum
conductance of any cut in the graph.

Throughout the paper, all vectors $\vec{x}\in\mathbb{R}^{n}$ are column
vectors. For a vector $\vec{x}\in\mathbb{R}^{n}$, we denote by
${\vec{x}}^{\mathsf{T}}$ the transpose of $\vec{x}$. For two vectors $\vec{x}$
and $\vec{y}$ in $\mathbb{R}^{n}$, $\langle\vec{x},\vec{y}\rangle$ denotes
their inner product.

We denote the $n\times n$ adjacency matrix of the input graph $G$ by $A$,
where $A_{ij}=1$, if $(i,j)\in E$ and $0$ otherwise. We let $D$ denote the
$n\times n$ diagonal degree matrix of $G$, where
$D_{ij}=\operatorname{deg}(i)$ if $i=j$ and $0$ otherwise.

The main technical tool in our analysis will be random walks on the input
graph $G$. We denote a random walk by its transition matrix $M$. For a pair of
vertices $u,v\in V$, we let $M_{uv}$ denote the probability of visiting $u$
from $v$ in one step of $M$. In the standard definition of a random walk,
$M_{uv}$ is defined as $1/\operatorname{deg}(v)$.

We will use a slightly modified version of the standard random walk called a
_lazy random walk_ in our work. A _lazy random walk_ currently stationed at
$v\in V$, stays at $v$ with probability $1/2$ and, with the remaining
probability $1/2$, it visits a neighbour of $v$ uniformly at random.

Let $M$ be a lazy random walk on $G$, the transition probabilities for $M$ are
defined as follows, For a pair $v,w\in V$ such that $v\neq w$,
$M_{vw}=\frac{1}{2\operatorname{deg}(w)}$, if $(v,w)\in E$ and $0$, otherwise.
Furthermore, for $v\in V$, we define $M_{vv}=1/2$. Algebraically, $M$ can be
expressed as

$M=\frac{1}{2}(I+AD^{-1}),$

where $I$ is the $n\times n$ identity matrix. Let $\pi$ denote the stationary
distribution of $M$. It is well known that in the stationary distribution of a
lazy random walk, each vertex is visited with probability proportional to its
degree. More formally,

$\pi=\frac{\vec{d}}{2m},$

where $\vec{d}$ is an $n$-dimensional vector of vertex degrees and $m$ is the
number of edges in $G$.

In the following we provide a brief exposition of relevant concepts from
spectral graph theory. We refer the reader to the textbook [5] by Fan Chung
for a detailed treatment of the subject.

Note that for irregular graphs $M$ is an asymmetric matrix and may not have an
orthogonal set of eigenvectors. For analyzing random walks on $G$ in terms of
the eigenvalues and eigenvectors of its associated matrices, we rely on a
related symmetric matrix called the _normalized Laplacian_ of $G$ denoted by
$N$. The normalized Laplacian $N$ is defined as

$N=I-D^{-1/2}AD^{-1/2}.$

We show below a way to express $M$ in terms of $N$.

$\displaystyle\begin{aligned}
M&=\frac{1}{2}(I+AD^{-1})=I-\frac{1}{2}(I-AD^{-1})\\\
&=I-\frac{1}{2}D^{1/2}(I-D^{-1/2}AD^{-1/2})D^{-1/2}\\\
&=I-\frac{1}{2}D^{1/2}ND^{-1/2}\\\ &=D^{1/2}(I-N/2)D^{-1/2}.\end{aligned}$

Since $N$ is a symmetric matrix, it has a set of $n$ real eigenvalues and a
corresponding set of mutually orthogonal eigenvectors. Throughout we let
$\omega_{1}\leq\omega_{2},\ldots,\omega_{n}$ denote the set of eigenvalues and
$\vec{\zeta}_{1},\vec{\zeta}_{2},\ldots,\vec{\zeta}_{n}$ denote the
corresponding set of eigenvectors. It is well known that eigenvalues of $N$
are $0=\omega_{1}\leq\omega_{2},\ldots,\omega_{n}\leq 2$. It is easy to verify
that $\sqrt{\vec{d}}$ is the first eigenvector $\vec{\zeta}_{1}$ of $N$ with
corresponding eigenvalue $\omega_{1}=0$. Each of the orthogonal eigenvectors
$\vec{\zeta}_{i}$ can be normalized to be a unit vector as
$\vec{e}_{i}=\frac{\vec{\zeta}_{i}}{\lVert\vec{\zeta}_{i}\rVert_{2}}$.
Together, these orthogonal unit eigenvectors define an orthonormal basis for
$\mathbb{R}^{n}$. Observe that the first unit eigenvector $\vec{e}_{1}$ of
this orthonormal basis is $\sqrt{\vec{d}}/\sqrt{2m}$. Also observe that the
stationary distribution $\pi$ of $M$ is equal to
$D^{1/2}\vec{e}_{1}/\sqrt{2m}$.

It is easy to verify that for every uint eigenvector $\vec{e}_{i}$ of $N$, we
have a corresponding right eigenvector $D^{1/2}\vec{e}_{i}$ of $M$ with
eigenvalue $1-\omega_{i}/2$.

On a connected, graph, a lazy random walk $M$ can be viewed as a reversible,
aperiodic Markov chain $\mathcal{M}_{G}$ with state space $V$ and transition
matrix $M$.

######  Definition 5.

Let $\mathcal{M}$ be a reversible, aperiodic Markov chain on a finite state
space $V$ with stationary distribution $\pi$. Furthermore, let
$\pi(S)=\sum_{v\in S}\pi(v)$. The Cheeger constant or conductance
$\phi(\mathcal{M})$ of the chain is defined as

$\phi(\mathcal{M})=\min_{S\subset V:\pi(S)\leq 1/2}\frac{\sum_{x\in S,y\in
V\setminus S}\pi(x)\mathcal{M}(y,x)}{\pi(S)}.$

Note that $\mathcal{M}(y,x)$ is the probability of moving to state $y$ from
state $x$ in one step.

The definition of the lazy random walk matrix $M$ and the the fact that the
stationary distribution $\pi$ of our lazy random walk is $\vec{d}/2m$ together
imply that the Cheeger constant $\phi(M)$ (henceforth, $\phi_{*}$) of the walk
$\mathcal{M}$ is

$\phi_{*}=\min_{U\in
V,\operatorname{vol}(U)\leq\operatorname{vol}(V)/2}\frac{E(U,V\setminus
U)}{2\cdot\operatorname{vol}(U)}.$

For an $\alpha$-conductor, we get that

$\phi_{*}=\frac{\alpha}{2}.$ (1)

We use the asymptotic notation $O_{d}()$ to indicate the dependency of a
quantity on the parameters other than the degree bound $d$.

##  3 A Distributed Algorithm for Testing Conductance

Given an input graph $G=(V,E)$, with $n$ vertices and $m$ edges, a conductance
parameter $\alpha$, and a distance parameter $\epsilon$, our distributed
conductance tester distinguishes, with high probability, between the case
where $G$ is an $\alpha$-conductor and the case where $G$ is $\epsilon$-far
from being an $\Omega(\alpha^{2})$-conductor. A key technical lemma from [20]
implies that, if $G$ is $\epsilon$-far from being an
$\Omega(\alpha^{2})$-conductor, then there exists a low-conductance cut
$(S,\overline{S})$ such that $\operatorname{vol}(S)\geq\epsilon m/10$. We
build on this lemma to show, using spectral methods (see Lemma 10 and
Corollary 11), that there exist a set of _sticky_ vertices with high enough
volume in $S$. Recall that a vertex $x$ in a low-conductance set $S$ is sticky
if there exists a large enough subset $T\subset S$ such that $x\in T$ and a
short random walk starting from $x$ _ends_ in $T$ with a sufficiently high
probability. Intuitively, random walks starting from sticky vertices tend to
stick to a small region around them. This leads to some vertex in the graph
receive more than their _fair share_ of number of walks. On the other, hand if
a graph is a good conductor, then the random walks from anywhere in the graph
mix very quickly. This ensures that the fraction of the total number of walks
received by any vertex in the graph is proportional to its degree.

We randomly sample a set $Q$ of $\Omega(1/\epsilon)$ _source_ vertices (each
vertex $v\in V$ is sampled with probability proportional to its degree). Then
we run a certain number of short random walks from each source in $Q$. Since a
large part of the volume of our high-volume, low-conductance set $S$ consists
of only sticky vertices in a bad conductor, some vertex in $Q$ will be sticky
with sufficiently large probability. We exploit the fact that some vertex near
a sticky vertex will see more number of walks than a pre-defined threshold and
we use the number of walks received by each vertex from a specific source as a
test criteria.

We implement sampling of the set $Q$ by having each vertex $v$ sample itself
by flipping a biased coin with probability
$5000\cdot\operatorname{deg}(v)/(\epsilon 2m)$. Therefore, we get that
$|Q|=5000/\epsilon$. It follows from Chernoff bound that the probability of
$Q$ having more than $5500/\epsilon$ vertices is at most $e^{-23/\epsilon}\leq
e^{-23}$. Then, we perform $K$ random walks of length $\ell$ starting from
each of the chosen vertices in $Q$. The exact values of these parameters are
specified later in the sequel. The entire algorithm is summarized in Algorithm
1. At any point before the last step of random walks, each vertex $v\in V$
contains a set $W$ of tuples $(q,count,i)$, where $count$ is the number of
walks of length $i$ originating from source $q$ currently stationed at $v$.
All these walks are advanced by one step (for $\ell$ times) by invoking
Algorithm 2. At the end of the last step of the walks, Algorithm 2 outputs a
set of tuples $C_{v}$. Each tuple in $C_{v}$ is of the form $(q,count)$, where
$count$ is the total number of $\ell$-step walks starting at $q$ that ended at
$v$. Then, in Algorithm 1, processor at vertex $v$ goes over every tuple
$(q,count)$ in $C_{v}$ (see Lines 11 to 15 of Algorithm 1), and if the $count$
value of any of them is above a pre-defined threshold $\tau$, it outputs
_Reject_. If none of the tuples have their $count$ value above threshold, it
outputs _Accept_. The exact value of $\tau$ is specified later in the sequel.

The implementation of (one step) of a separate set of random walks from each
of the starting points in $Q$ is described in Algorithm 2. when advancing the
walks originating at a source $q\in Q$ by one step, we do not send the full
trace of every random walk. Instead, for every source $q\in Q$, every vertex
$v\in V$ only sends a tuple $(q,k,i)$ to its neighbour $w$ indicating that $k$
random walks originating at $q$ have chosen $w$ as their destination in their
$i$th step. Since the size of $Q$ is constant with high enough probability, we
will not have to send more than a constant number of such tuples on each edge.
Moreover, each tuple can be encoded using $O(\log n)$ bits (given the values
of parameters $\ell$ and $K$ specified in the sequel). Hence, we only
communicate $O(\log n)$ bits per edge in any round with high probability. To
make sure we do not congest any edge, we check the length of every message
(see lines 16 to 18 of Algorithm 2) before we send it. If a message appears
too large to send, we simply output _Reject_ on the host vertex and abort the
algorithm. Note that the number of tuples we ever have to send along any edge
is upper bounded by $|Q|$ and $|Q|\leq 5500\epsilon$, with probability at
least $1-e^{-23}$. Therefore, we may rarely abort the algorithm before
completing the execution of the random walks. If that happens, then the
probability of accepting an $\alpha$-conductor is slightly reduced. Hence the
following observation follows:

######  Observation 6.

Algorithm 1 rejects an $\alpha$-conductor due to congestion with probability
at most $e^{-23}$.

We set the required parameters of Algorithm 1 as follows:

  * •

the number of walks $K=2m^{2}$,

  * •

the length of each walk $\ell=\frac{32}{\alpha^{2}}\log n$

  * •

the rejection threshold for vertex $v\in V$,
$\tau_{v}=m\cdot\operatorname{deg}(v)\cdot(1+2n^{-1/4})$.

Algorithm 1 Distributed algorithm running at vertex $v$ for testing
conductance.

1:Algorithm Distributed-Graph-Conductance-Test($G,\epsilon,\alpha,\ell,K$)

2:$\triangleright$ The algorithm performs $K$ random walks of length $\ell$
from a set $Q$ of $\Theta(1/\epsilon)$ starting vertices, where every starting
vertex is sampled randomly from $V$.

3: $\ell$ : The length of each random walk

4: $K$ : The number of walks

5: $W_{v}$ : Set of tuples $(q,count,i)$ $\triangleright$ where $count$ is the
number of walks originating at source $q$ currently stationed at $v$

6: $C_{v}$ : Set of tuples $(q,count)$ $\triangleright$ where $count$ is the
total number of $\ell$ step walks starting at $q$ that ended at $v$

7: $\tau_{v}$ : maximum number of $\ell$-length walks $v$ should see from a
given source on an $\alpha$-conductor.

8: Flip a biased coin with probability $p=5000\operatorname{deg}(v)/(\epsilon
2m)$ to decide whether to start $K$ lazy random walks.

9: If chosen, initialise $W_{v}$ as $W_{v}\leftarrow\\{(v,K,0)\\}$.

10: Call Algorithm 2 for $\ell$ synchronous rounds.

11: while there is some tuple $(q,count)$ in $C_{v}$ do

12: if $count>\tau_{v}$ then $\triangleright$ Received too many walks from
$q$.

13: Output _Reject_ and stop all operations.

14: else

15: Remove $(q,count)$ from $C_{v}$

16: Output _Accept_

Algorithm 2 Algorithm for moving random walks stationed at $v$ by one step.

1:Algorithm Move-Walks-At-$v$

2: $W_{v}$ : Set of tuples $(q,count,i)$ $\triangleright$ where $count$ is the
number of walks originating at source $q$ currently stationed at $v$ just
after their $i$th step..

3: $D_{v}$ : Set of tuples $(q,count,dest)$ $\triangleright$ where $count$ is
the number of walks starting at $q$ that are to be forwarded to $dest$.

4: $C_{v}$ : Set of tuples $(q,count)$ $\triangleright$ where $count$ is the
total number of walks starting at $q$ that have $v$ as their final destination
or endpoint.

5: $D_{v}\leftarrow\emptyset$.

6: while there is some tuple $(q,k,i)$ in $W_{v}$ do

7: if $i\neq L$ then $\triangleright$ If not the last step, process the next
set of destinations.

8: Draw the next set of destinations for the $k$ walks and update the set
$D_{v}$.

9: Remove $(q,k,i)$ from $W_{v}$

10:$\triangleright$ If last step of the walks, update how many ended at $v$.

11: Update $C_{v}$ to reflect the $k$ walks that ended in $v$.

12:$\triangleright$ Prepare the messages to be sent

13: while there is some tuple $(q,count,dest)$ in $D_{v}$ do

14: Add tuple $(q,count,i+1\rangle$ to the message to be sent to $dest$

15:$\triangleright$ Check each message for length

16: For each message $M$ to be sent

17: if the number of tuples in $M>5500/\epsilon$ then

18: Output _Reject_ and stop all operations.

19: Send all the messages to their respective destinations.

20:$\triangleright$ Process the messages received

21: For each source $s$ from which a total of $s_{count}$ walks are received,

22:add tuple $(s,s_{count},i+1)$ to $W_{v}$

###  3.1 Analysis of the Algorithm

In this section, we show that Algorithm 1 accepts every $\alpha$-conductor
with probability at least $2/3$, and rejects every graph that is
$\epsilon$-far from being an $\alpha^{*}$-conductor, where
$\alpha^{*}=\Theta({\alpha^{2}})$, with probability at least $2/3$.

The main idea behind our algorithm is that, in a bad conductor, a random walk
would converge to the stationary distribution more slowly and would initially
get trapped within sets of vertices with small conductance.

Next, we provide a lower bound for the probability of an $\ell$-step random
walk starting from a vertex chosen at random (with probability proportional to
its degree) from a subset $T$ of a low-conductance set $S$ finishing at some
vertex in $T$.

######  Definition 7.

For a set $T\subseteq V$, and a vertex $u\in T$, let
$\operatorname{trap}(u,T,\ell)$ (henceforth _trap probability_) denote the
probability of an $\ell$-step random walk starting from $u\in T$ finishing at
some vertex in $T$. When the starting vertex is chosen at random from $T$ with
probability proportional to its degree, we denote by
$\operatorname{trap}(T,\ell)$ the average trap probability (weighted by vertex
degrees) over set $T$:

$\operatorname{trap}(T,\ell)=\frac{1}{\operatorname{vol}(T)}\sum_{u\in
T}\operatorname{deg}(u)\cdot\operatorname{trap}(u,T,\ell).$

Given a set $S$ of conductance at most $\delta$ and $T\subseteq S$, we
establish a relationship between the average trap probability
$\operatorname{trap}(T,\ell)$ and conductance bound $\delta$ of $S$ in the
next two lemmas. We first consider the case $T=S$ in Lemma 8, and then obtain
a bound when $T$ is a subset (of sufficiently large volume) of $S$ in Lemma
10.

######  Lemma 8.

Consider a set $S\subseteq V$, such that the cut $(S,\overline{S})$ has
conductance at most $\delta$. Then, for any integer $\ell>0$, the following
holds

$\operatorname{trap}(S,\ell)\geq\frac{\operatorname{vol}(S)}{2m}+\left(\frac{5}{6}-\frac{\operatorname{vol}(S)}{2m}\right)(1-3\delta)^{\ell}.$

###### Proof.

Let ${\mathbbm{1}_{S}}$ denote the $n$-dimensional indicator vector of set
$S$. We pick a source vertex $v\in S$ with probability
$\operatorname{deg}(v)/\operatorname{vol}(S)$, where $\operatorname{deg}(v)$
is degree of $v$ and $\operatorname{vol}(S)$ is the sum of degrees of vertices
in set $S$. This defines an initial probability distribution denoted by
$\vec{p}^{\,0}_{S}$ on the vertex set $V$, where,
$\vec{p}^{\,0}_{S}(v)=d(v)/\operatorname{vol}(S)$ for $v\in S$ and
$\vec{p}^{\,0}_{S}=0$ for $v\notin S$. Note that
$\vec{p}^{\,0}_{S}=\frac{1}{\operatorname{vol}(S)}D{\mathbbm{1}_{S}}$, where,
$D$ is the diagonal degree matrix of $G$. Denote by $M$ the transition matrix
of a lazy random walk on $G$.

The endpoint probability distribution $\vec{p}^{\,\ell}_{S}$ of an $\ell$-step
lazy random walk on $G$ starting from a vertex chosen from $S$ according to
$\vec{p}^{\,0}_{S}$ is given by

$\vec{p}_{S}^{\,\ell}=M^{\ell}\vec{p}^{\,0}_{S}=\frac{1}{\operatorname{vol}(S)}M^{\ell}D{\mathbbm{1}_{S}}.$

Recall that $M$ can be expressed in terms of the normalized Laplacian matrix
$N=I-D^{-1/2}AD^{-1/2}$ of $G$ as $M=D^{1/2}(I-\frac{N}{2})D^{-1/2}$. (See
Section 2.) It follows therefore that

$\vec{p}_{S}^{\,\ell}=\frac{1}{\operatorname{vol}(S)}\left(D^{1/2}\left(I-\frac{N}{2}\right)D^{-1/2}\right)^{\ell}D{\mathbbm{1}_{S}}.$

The trap probability $\operatorname{trap}(S,\ell)$ of an $\ell$-step lazy
random walk starting from a random vertex in $S$ picked according to
$\vec{p}^{\,0}_{S}$ can be expressed as the inner product of vectors
$\vec{p}_{S}^{\,\ell}$ and ${\mathbbm{1}_{S}}$:

$\displaystyle\begin{aligned}
\operatorname{trap}(S,\ell)&=\frac{1}{\operatorname{vol}(S)}\mathbbm{1}_{S}^{\mathsf{T}}M^{\ell}D{\mathbbm{1}_{S}}\\\
&=\frac{1}{\operatorname{vol}(S)}\mathbbm{1}_{S}^{\mathsf{T}}\left(D^{1/2}\left(I-\frac{N}{2}\right)D^{-1/2}\right)^{\ell}D{\mathbbm{1}_{S}}\\\
&=\frac{1}{\operatorname{vol}(S)}{(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}\left(I-\frac{N}{2}\right)^{\ell}(D^{1/2}{\mathbbm{1}_{S}}).\end{aligned}$

Recall that $0=\omega_{1}\leq\omega_{2}\leq\ldots\leq\omega_{n}<2$ are the
eigenvalues of $N$ and $\vec{e}_{1},\vec{e}_{2},\ldots,\vec{e}_{n}$ denote the
corresponding unit eigenvectors (see Section 2). We can express
$D^{1/2}{\mathbbm{1}_{S}}$ in the orthonormal basis defined by the
eigenvectors of $N$ as
$D^{1/2}{\mathbbm{1}_{S}}=\sum_{i}\alpha_{i}\vec{e}_{i}$. It follows that

$\sum_{i}\alpha_{i}^{2}=\langle
D^{1/2}{\mathbbm{1}_{S}},D^{1/2}{\mathbbm{1}_{S}}\rangle=\operatorname{vol}(S).$
(2)

Taking the quadratic form of $N$ for vector $D^{1/2}{\mathbbm{1}_{S}}$, we get

$\displaystyle\begin{aligned}
{(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}N(D^{1/2}{\mathbbm{1}_{S}})&={(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}I(D^{1/2}{\mathbbm{1}_{S}})-{(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}(D^{-1/2}AD^{-1/2})(D^{1/2}{\mathbbm{1}_{S}})\\\
&=\operatorname{vol}(S)-{(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}(D^{-1/2}AD^{-1/2})(D^{1/2}{\mathbbm{1}_{S}})\\\
&=\operatorname{vol}(S)-\mathbbm{1}_{S}^{\mathsf{T}}A{\mathbbm{1}_{S}}.\end{aligned}$

Note that the term $\mathbbm{1}_{S}^{\mathsf{T}}A{\mathbbm{1}_{S}}$
corresponds to the number of edges in $S\times S$. Therefore. it follows that

${(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}N(D^{1/2}{\mathbbm{1}_{S}})=E(S,\overline{S}).$
(3)

Since the conductance of the cut $(S,\overline{S})$ is less than $\delta$, we
have that

${(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}N(D^{1/2}{\mathbbm{1}_{S}})=E(S,\overline{S})\leq\delta\cdot\operatorname{vol}(S).$
(4)

Expressing $D^{1/2}{\mathbbm{1}_{S}}$ as $\sum_{i}\alpha_{i}\vec{e}_{i}$, the
quadratic form of $N$ for $D^{1/2}{\mathbbm{1}_{S}}$ can also be written as

${(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}N(D^{1/2}{\mathbbm{1}_{S}})={(\sum_{i}\alpha_{i}\vec{e}_{i})}^{\mathsf{T}}N(\sum_{i}\alpha_{i}\vec{e}_{i})=\sum_{i}\alpha_{i}^{2}\omega_{i}.$
(5)

Combining from Eq.s (2), (4) and (5), we get that

${(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}(I-\frac{N}{2})(D^{1/2}{\mathbbm{1}_{S}})=\sum_{i}\alpha_{i}^{2}-\frac{1}{2}\sum_{i}\alpha_{i}^{2}\omega_{i}\geq\operatorname{vol}(S)-\frac{\delta}{2}\operatorname{vol}(S).$
(6)

Recall that $0=\omega_{1}\leq\omega_{2}\leq\ldots\leq\omega_{n}<2$ are the
eigenvalues of $N$ and let $\vec{e}_{1},\vec{e}_{2},\ldots,\vec{e}_{n}$ be the
corresponding unit eigenvectors. Correspondingly, we can define a set of
eigenvalues $1=\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}>0$ and the
same set of eigenvectors $\vec{e}_{1},\vec{e}_{2},\ldots,\vec{e}_{n}$ for
$I-N/2$. Notice that for each $i$, $\lambda_{i}=1-\omega_{i}/2$. With this
translation of eigenspace, we get that

${(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}(I-\frac{N}{2})(D^{1/2}{\mathbbm{1}_{S}})=\sum_{i}\alpha_{i}^{2}\lambda_{i}.$

We call the quantity $\sum_{i}\alpha_{i}^{2}$ the _coefficient sum of the
eigenvalue set_. We also call an eigenvalue $\lambda_{i}$ of $I-N/2$ (and the
corresponding eigenvector $\vec{e}_{i}$) _heavy_ if $\lambda_{i}\geq
1-3\delta$. We denote by $H$ the index set of the heavy eigenvalues and let
$\overline{H}$ be the index set of the rest. Since
$\sum_{i}\alpha_{i}^{2}\lambda_{i}\geq(1-\delta/2)\operatorname{vol}(S)$ is
large for a set with small conductance, we expect many of the coefficients
$\alpha_{i}^{2}$ corresponding to heavy eigenvalues to be large. This would
slow down the convergence of the random walk and make the trap probability for
our low-conductance set $S$ large. The following claim establishes a lower
bound on the contribution of the index set $H$ to the coefficient sum.

######  Claim 9.

For $\\{\alpha_{i}\\}_{i},H$, and $s$ as defined above,

$\sum_{i\in H}\alpha_{i}^{2}\geq\frac{5}{6}\operatorname{vol}(S).$

###### Proof.

Let $x$ denote the coefficient sum of the set $H$ of heavy eigenvalues: that
is,

$x\coloneqq\sum_{i\in H}\alpha_{i}^{2}.$

The following expression follows by the definition of the set $H$ and its
coefficient sum $x$:

$\sum_{i}\alpha_{i}^{2}\lambda_{i}=\sum_{i\in
H}\alpha_{i}^{2}\lambda_{i}+\sum_{i\in\overline{H}}\alpha_{i}^{2}\lambda_{i}\leq
x+(\sum_{i}\alpha_{i}^{2}-x)(1-3\delta).$

The second inequality above follows by upper bounding every $\lambda_{i}$ with
$i\in H$ by $1$ and every $\lambda_{i}$ with $i\in\overline{H}$ by
$1-3\delta$. Recall that $\sum_{i}\alpha_{i}^{2}=\langle
D^{1/2}{\mathbbm{1}_{S}},D^{1/2}{\mathbbm{1}_{S}}\rangle=\operatorname{vol}(S)$
and we just proved that
$\sum_{i}\alpha_{i}^{2}\lambda_{i}\geq(1-\delta/2)\operatorname{vol}(S)$ in
(6). It follows that

$(1-\delta/2)\operatorname{vol}(S)\leq\sum_{i}\alpha_{i}^{2}\lambda_{i}\leq
x+(\operatorname{vol}(S)-x)(1-3\delta).$

Rearranging the inequality above, we get that $x\geq
5\operatorname{vol}(S)/6$. ∎

Next, we use Claim 9 to get a lower bound on the average trap probability of
set $S$ in terms of the conductance of the cut $(S,\overline{S})$.

$\displaystyle\begin{aligned}
\operatorname{trap}(S,\ell)&=\frac{1}{\operatorname{vol}(S)}{(D^{1/2}{\mathbbm{1}_{S}})}^{\mathsf{T}}(I-\frac{N}{2})^{\ell}(D^{1/2}{\mathbbm{1}_{S}})\\\
&=\frac{1}{\operatorname{vol}(S)}{(\sum_{i}\alpha_{i}\vec{e}_{i})}^{\mathsf{T}}(I-\frac{N}{2})^{\ell}(\sum_{i}\alpha_{i}\vec{e}_{i})\\\
&=\frac{1}{\operatorname{vol}(S)}{(\sum_{i}\alpha_{i}\vec{e}_{i})}^{\mathsf{T}}(\sum_{i}\alpha_{i}\lambda_{i}^{\ell}\vec{e}_{i})=\frac{1}{\operatorname{vol}(S)}\sum_{i}\alpha_{i}^{2}\lambda_{i}^{\ell}.\end{aligned}$

Furthermore, focusing on the contribution of the index set $H$ to the trap
probability,

$\displaystyle\operatorname{trap}(S,\ell)$
$\displaystyle=\frac{1}{\operatorname{vol}(S)}\sum_{i}\alpha_{i}^{2}\lambda_{i}^{\ell}$
$\displaystyle\geq\frac{1}{\operatorname{vol}(S)}\sum_{i\in
H}\alpha_{i}^{2}\lambda_{i}^{\ell}$
$\displaystyle=\frac{1}{\operatorname{vol}(S)}\left(\alpha_{1}^{2}\lambda_{1}+\sum_{i\in
H\setminus\\{1\\}}\alpha_{i}^{2}\lambda_{i}^{\ell}\right)$
$\displaystyle\geq\frac{1}{\operatorname{vol}(S)}\left(\alpha_{1}^{2}+\left(\frac{5\operatorname{vol}(S)}{6}-\alpha_{1}^{2}\right)\left(1-3\delta\right)^{\ell}\right).$
(7)

The last inequality follows by the definition of a heavy eigenvalue and by
Claim 9 (we have that $\sum_{i\in H}\alpha_{i}^{2}\geq
5\operatorname{vol}(S)/6$). By definition, $\lambda_{1}=1$ and
$\vec{e}_{1}=\sqrt{\vec{d}}/\sqrt{2m}$, where, $\vec{d}$ is the vector of
vertex degrees. It follows that

$\alpha_{1}=\langle
D^{1/2}{\mathbbm{1}_{S}},\vec{e}_{1}\rangle=\operatorname{vol}(S)/\sqrt{2m}.$

Plugging in the values of $\alpha_{1}$ in (7), we get

$\displaystyle\operatorname{trap}(S,\ell)$
$\displaystyle\geq\frac{1}{\operatorname{vol}(S)}\left(\frac{(\operatorname{vol}(S))^{2}}{2m}+\left(\frac{5\operatorname{vol}(S)}{6}-\frac{(\operatorname{vol}(S))^{2}}{2m}\right)\left(1-3\delta\right)^{\ell}\right)$
$\displaystyle=\frac{\operatorname{vol}(S)}{2m}+\left(\frac{5}{6}-\frac{\operatorname{vol}(S)}{2m}\right)(1-3\delta)^{\ell}.$

Therefore, we can conclude that there exists a vertex $v\in S$ such that

$\operatorname{trap}(v,S,\ell)\geq\frac{\operatorname{vol}(S)}{2m}+\left(\frac{5}{6}-\frac{\operatorname{vol}(S)}{2m}\right)(1-3\delta)^{\ell}.\qed$

Next, we prove that every subset $T\subset S$ of large enough volume has high
trap probability. More specifically, we prove a lower bound on the probability
of an $\ell$-step random walk starting from a vertex chosen at random (with
probability proportion to its degree) from $T$ finishing at some vertex in
$T$.

######  Lemma 10.

Consider sets $T\subseteq S\subseteq V$, such that the cut $(S,\overline{S})$
has conductance at most $\delta$ and that
$\operatorname{vol}(T)=(1-\eta)\operatorname{vol}(S)$ for some $0<\eta<5/6$,
then for any integer $\ell>0$, the following holds

$\operatorname{trap}(T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\left(\frac{5}{6}\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}-\frac{\operatorname{vol}(T)}{2m}\right)(1-3\delta)^{\ell}.$

###### Proof.

Let ${\mathbbm{1}_{S}}$ and ${\mathbbm{1}_{T}}$ denote the $n$-dimensional
indicator vectors of sets $S$ and $T$, respectively. As in the proof of Lemma
8, we express $D^{1/2}{\mathbbm{1}_{S}}$ and $D^{1/2}{\mathbbm{1}_{T}}$ in the
orthonormal basis defined by the eigenvectors of the normalized Laplacian
matrix $N$ as $D^{1/2}{\mathbbm{1}_{S}}=\sum_{i}\alpha_{i}\vec{e}_{i}$ and
$D^{1/2}{\mathbbm{1}_{T}}=\sum_{i}\beta_{i}\vec{e}_{i}$.

Since the conductance of the cut $(S,\overline{S})$ is at most $\delta$, Claim
9 from Lemma 8 holds. We have that

$\sum_{i}\alpha_{i}^{2}\geq\sum_{i\in
H}\alpha_{i}^{2}\geq\frac{5}{6}\operatorname{vol}(S).$

By the definition of $D^{1/2}{\mathbbm{1}_{S}}$ and
$D^{1/2}{\mathbbm{1}_{T}}$, we have

$\lVert
D^{1/2}{\mathbbm{1}_{S}}-D^{1/2}{\mathbbm{1}_{T}}\rVert_{2}^{2}=\operatorname{vol}(S)-\operatorname{vol}(T)=\operatorname{vol}(S)-(1-\eta)\cdot\operatorname{vol}(S)=\eta\cdot\operatorname{vol}(S).$

Furthermore, the following follows from the expression of
$D^{1/2}{\mathbbm{1}_{S}}$ and $D^{1/2}{\mathbbm{1}_{T}}$ in terms of the
eigenvectors of $I-N/2$:

$\eta\cdot\operatorname{vol}(S)=\lVert
D^{1/2}{\mathbbm{1}_{S}}-D^{1/2}{\mathbbm{1}_{T}}\rVert_{2}^{2}=\sum_{i}(\alpha_{i}-\beta_{i})^{2}.$

Applying the triangle inequality,
$\lVert\vec{a}-\vec{b}\rVert\geq\lVert\vec{a}\rVert-\lVert\vec{b}\rVert$ and
upper bounding $\sqrt{\sum_{i\in H}(\alpha_{i}-\beta_{i})^{2}}$ by
$\sqrt{\sum_{i}(\alpha_{i}-\beta_{i})^{2}}=\sqrt{\eta\cdot\operatorname{vol}(S)}$,
we get that

$\displaystyle\begin{aligned} \sum_{i\in
H}\beta_{i}^{2}\geq&\left(\sqrt{\sum_{i\in H}\alpha_{i}^{2}}-\sqrt{\sum_{i\in
H}\left(\alpha_{i}-\beta_{i}\right)^{2}}\right)^{2}\\\
\geq&\left(\sqrt{\frac{5}{6}\operatorname{vol}(S)}-\sqrt{\eta\cdot\operatorname{vol}(S)}\right)^{2}=\frac{5}{6}\operatorname{vol}(S)\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}.\end{aligned}$

Reasoning as in Lemma 8 and applying $\lambda_{i}\geq(1-3\delta)$, for all
$i\in H$, we can bound the average trap probability over set $T$ as

$\displaystyle\begin{aligned}
\operatorname{trap}(T,\ell)\geq&\frac{1}{\operatorname{vol}(T)}\sum_{i\in
H}\beta_{i}^{2}\lambda_{i}^{\ell}=\frac{1}{\operatorname{vol}(T)}\left(\beta_{1}^{2}\lambda_{1}+\sum_{i\in
H\setminus\\{1\\}}\beta_{i}^{2}\lambda_{i}^{\ell}\right)\\\
\geq&\frac{1}{\operatorname{vol}(T)}\left(\frac{(\operatorname{vol}(T))^{2}}{2m}+\left(\frac{5\operatorname{vol}(S)}{6}\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}-\frac{(\operatorname{vol}(T))^{2}}{2m}\right).(1-3\delta)^{\ell}\right)\\\
=&\frac{\operatorname{vol}(T)}{2m}+\left(\frac{5}{6}\cdot\frac{\operatorname{vol}(S)}{\operatorname{vol}(T)}\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}-\frac{\operatorname{vol}(T)}{2m}\right)(1-3\delta)^{\ell}.\end{aligned}$
(8)

The second-to-last inequality follows from the definition of the first
eigenvalue, eigenvector pair of matrix $I-N/2$. By definition, $\lambda_{1}=1$
and $\vec{e}_{1}=d^{1/2}/\sqrt{2m}$. Therefore, we have that
$\beta_{1}=\langle
D^{1/2}{\mathbbm{1}_{T}},\vec{e}_{1}\rangle=\operatorname{vol}(T)$. Since
$T\subseteq S$, $\operatorname{vol}(S)/\operatorname{vol}(T)\geq 1$. The lemma
follows by substituting $\operatorname{vol}(S)/\operatorname{vol}(T)$ by its
lower bound $1$ in (8). ∎

Lemma 10 implies that any subset $T$ (of sufficiently large volume) of a low-
conductance set $S\subseteq V$ contains at least one vertex $v\in T$ such that
a random walk starting from $v$ ends in $T$ with sufficiently high
probability, i.e., $v$ is sticky. More precisely, there exists a sticky vertex
$v\in T$ such that

$\operatorname{trap}(v,T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\left(\frac{5}{6}\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}-\frac{\operatorname{vol}(T)}{2m}\right)(1-3\delta)^{\ell}.$
(9)

This leads to the following corollary as a result:

######  Corollary 11.

Consider a set $S\subset V$, such that the cut $(S,\overline{S})$ has
conductance at most $\delta$. Given any $0<\eta<5/6$ and integer $\ell>0$,
there exist a set of volume at least $\eta\cdot\operatorname{vol}(S)$, such
that every vertex in this set is sticky. In other words, for every vertex $v$
is this set, there exists $T\subseteq S$ of volume
$\operatorname{vol}(T)=(1-\eta)\cdot\operatorname{vol}(S)$ such that

$\operatorname{trap}(v,T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\left(\frac{5}{6}\left(1-\sqrt{\frac{6\eta}{5}}\right)^{2}-\frac{\operatorname{vol}(T)}{2m}\right)(1-3\delta)^{\ell}.$

###### Proof.

Let $P\subseteq S$ denote the set of all the vertices for which eq (9) holds
for some set $T$. One can extract $P$ using the following iterative procedure.
To begin with, we pick an arbitrary subset $T$ of volume
$(1-\eta)\cdot\operatorname{vol}(S)$ from $S$. By Lemma 10, there exists a
vertex $v$ in $T$ with the desired trap probability. We remove $v$ from $S$
and add it to $P$. Let $R$ be the set of remaining vertices of $S$. We then
extract another subset $T$ of volume $(1-\eta)\cdot\operatorname{vol}(S)$ from
$R$ and this process continues until we do not have sufficient volume left in
$R$. It is easy to see that
$\operatorname{vol}(R)<(1-\eta)\cdot\operatorname{vol}(S)$ when this process
ends. This implies that the volume of $P$ is at least
$\eta\cdot\operatorname{vol}(S)$. ∎

We build on the following combinatorial lemma from [20]:

######  Lemma 12 (Lemma 9 of [20]).

Let $G=(V,E)$ be an $m$-edge graph. If there exists a set $P\subseteq V$ such
that $\operatorname{vol}(P)\leq\epsilon m/10$ and the subgraph $G[V\setminus
P]$ has conductance at least $\phi^{\prime}$, then there exists an algorithm
that modifies at most $\epsilon m$ edges of $G$ to get a graph
$G^{\prime}=(V,E^{\prime})$ with conductance at least $\phi/^{\prime}3$.

In the following lemma, we show the existence of a high volume set $A$ with
low enough conductance of cut $(A,\overline{A})$ in a graph that is far from
being a good conductor.

######  Lemma 13.

Let $G=(V,E)$ be an $n$-vertex, $m$-edge graph such that $G$ is $\epsilon$-far
from having conductance at least $\alpha^{2}/2880$, then there exists a set
$A\subseteq V$ such that $\operatorname{vol}(A)\geq\epsilon m/10$ and
conductance of cut $(A,\overline{A})$ is at most $\alpha^{2}/960$.

###### Proof.

We build the set $A$ iteratively from sets $A_{1},A_{2},\ldots,A_{i},\ldots$
as follows. We begin with $A=A_{0}=\emptyset$ and $\overline{A}_{0}=V$. In
iteration $i$, we look for a cut $(A_{i},\overline{A}_{i})$ in
$\overline{A}_{i-1}$ such that
$\operatorname{vol}(A_{i})\leq\operatorname{vol}(\overline{A_{i}})$ and
conductance of cut $(A_{i},\overline{A}_{i})$ is at most $\alpha^{2}/960$. We
set $A=A\cup A_{i}$ and $\overline{A}_{i}=\overline{A}_{i-1}\setminus A_{i}$.
This process continues until we can find such a cut in $A_{i-1}$. It follows
from the procedure that the conductance of the cut $(A,\overline{A})$ when we
stop is at most $\alpha^{2}/960$.

Next, we claim that the volume of the set $A$ is at least $\epsilon m/10$. Let
us assume for contradiction that $\operatorname{vol}(A)<\epsilon m/10$. Then,
by Lemma 12, with at most $\epsilon m$ edge updates, we can get a graph
$G^{\prime}$ with conductance at least $\alpha^{2}/2880$ from $G$. But we know
from the statement of the lemma that $G$ is $\epsilon$-far from having
conductance at least $\alpha^{2}/2880$. Hence, the claim follows by
contradiction. ∎

Finally, we need the following classical relation between the conductance or
Cheeger constant of a Markov chain and its second largest eigenvalue.

######  Theorem 14 ([2, 1, 8]).

Let $P$ be a reversible lazy chain (i.e., for all $x$, $P(x,x)\geq 1/2$) with
Cheeger constant $\phi_{*}$. Let $\lambda_{2}$ be the second largest
eigenvalue of $P$. Then,

$\frac{\phi_{*}^{2}}{2}\leq 1-\lambda_{2}\leq 2\phi_{*}.$

We can now state our main theorem.

######  Theorem 15.

For an input graph $G=(V,E)$, and parameters $0<\alpha<1$ and $\epsilon>0$,
Distributed-Graph-Conductance-Test in Algorithm 1

  * •

outputs Accept, with high probability at least $2/3$, on every vertex of $G$
if $G$ is an $\alpha$-conductor.

  * •

outputs Reject, with probability at least $2/3$, on at least one vertex of $G$
if $G$ is $\epsilon$-far from any $(\alpha^{2}/2880)$-conductor.

The algorithm uses $O(\log n)$ communication rounds.

###### Proof.

Let us start by showing that, with high probability, the algorithm outputs
_Accept_ on every vertex if $G$ is an $\alpha$-conductor. By Observation 6, we
may reject $G$ and abort the algorithm due to congestion with probability at
most $e^{-23}$. For now, let us assume that this event did not occur. Denote
by $\lambda_{2}$ the second largest eigenvalue of the lazy random walk matrix
$M$ on $G$. It is well known (see, e.g., [25]) that, for a pair $u,v\in V$,

$\left|M^{\ell}(v,u)-\frac{\operatorname{deg}(v)}{2m}\right|\leq\lambda^{\ell}_{2}\leq
e^{-\ell(1-\lambda_{2})}.$

Furthermore, it follows from Theorem 14 that

$\left|M^{\ell}(v,u)-\frac{\operatorname{deg}(v)}{2m}\right|\leq
e^{-\ell\phi^{2}_{*}/2}\leq e^{-\frac{\ell\alpha^{2}}{8}},$

where the second inequality above follows from the fact that, for a random
walk on an $\alpha$-conductor, $\phi_{*}=\alpha/2$ (see (1) in Section 2).
Thus, in an $\alpha$-conductor, for $\ell=(32/\alpha^{2})\log n$, any starting
vertex $u\in V$ and a fixed vertex $v\in V$, we have that

$\frac{\operatorname{deg}(v)}{2m}-\frac{1}{n^{4}}\leq
M^{\ell}(v,u)\leq\frac{\operatorname{deg}(v)}{2m}+\frac{1}{n^{4}}.$

Recall that the number $K$ of random walks and rejection threshold $\tau_{v}$
for vertex $v$ are set as $K=2m^{2}$ and
$\tau_{v}=m\cdot\operatorname{deg}(v)\cdot(1+2n^{-1/4})$.

Let $X_{u,v}$ denote the number of random walks starting from $u$ that ended
in $v$. It follows that

$\mathbb{E}X_{u,v}=K\cdot M^{\ell}(v,u)\leq
2m^{2}\cdot\frac{\operatorname{deg}(v)}{2m}+\frac{2m^{2}}{n^{4}}\leq
m\cdot\operatorname{deg}(v)+1.$

The random variable $X_{u,v}$ is the sum of $K$ independent Bernoulli trials
with success probability $M^{\ell}(v,u)$. Applying multiplicative Chernoff
bounds, we get the following for large enough $n$.

$\displaystyle\begin{aligned}
\Pr[X_{u,v}>(1+n^{-1/4})\cdot\mathbb{E}[X_{u,v}]]&<\exp\left(-n^{-1/2}\cdot(m\cdot\operatorname{deg}(v)+1)/3\right)\\\
&\leq\exp\left(-n^{-1/2}\cdot n/3\right)\\\ &=\exp\left(-n^{1/2}/3\right)\leq
n^{-2}.\end{aligned}$

The second inequality above follows from the fact that
$m\cdot\operatorname{deg}(v)>n-1$ for a connected graph. Thus, each vertex $y$
receives at most

$(1+n^{-1/4})\cdot\mathbb{E}[X_{u,v}]\leq(1+n^{-1/4})\cdot(m\cdot\operatorname{deg}(v)+1)<m\cdot\operatorname{deg}(v)+2m/n^{1/4}\cdot\operatorname{deg}(v)$

walks from $u$, with probability at least $1-n^{-2}$. Taking union bound over
all $y\in V$ and all starting vertices $u$, we get that, conditioned on the
event that we did not abort due to congestion, with high probability, our
algorithm outputs _Accept_ on every vertex of $G$ for every starting point if
$G$ is an $\alpha$-conductor. Finally, taking the union bound over the events
that we rejected due to congestion or due to receiving too many walks at some
vertex, the claim follows.

Next, we show that our algorithm rejects, with high probability, any graph $G$
that is $\epsilon$-far from being an $\alpha^{*}$-conductor, for
$\alpha^{*}=\alpha^{2}/2880$. By Lemma 13, there exists a set $S\subset V$,
with $\operatorname{vol}(S)\geq\epsilon m/10$, such that the conductance of
$S$ is less than $\alpha^{2}/960$. Further applying Corollary 11 with
$\eta=\frac{5}{6}\cdot\frac{1}{9^{2}}$ on $S$ as above, we get that there
exists a set $P$ of sticky vertices such that $\operatorname{vol}(P)\geq
5\operatorname{vol}(S)/486$ and for every $v\in P$, there exists a set
$T\subseteq S$, $\operatorname{vol}(T)=\frac{481}{486}\operatorname{vol}(S)$,
such that

$\operatorname{trap}(v,T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\left(\frac{160}{243}-\frac{\operatorname{vol}(T)}{2m}\right)\cdot\left(1-\frac{\alpha^{2}}{320}\right)^{\ell}\geq\frac{\operatorname{vol}(T)}{2m}+\left(\frac{160}{243}-\frac{\operatorname{vol}(T)}{2m}\right)\cdot{e}^{-\alpha^{2}\ell/160},$

where the last inequality follows from that $1-x>e^{-2x}$, for $0\leq x<1/2$,
provided that $\alpha^{2}/320\leq 1/2$. For $\ell=(32/\alpha^{2})\log n$ and
$\operatorname{vol}(T)\leq\operatorname{vol}(S)\leq\operatorname{vol}(V)/2=m$,
we get that, for every $v\in P$,

$\operatorname{trap}(v,T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\frac{77}{486}\cdot\frac{1}{n^{1/5}}.$

Let us assume that a vertex $u\in P\subset A$ is picked as the starting vertex
of $K=2m^{2}$ random walks in $G$. By Corollary 11 and above exposition, a set
$T$ with $\operatorname{vol}(T)=481\operatorname{vol}(S)/486$ with
$\operatorname{trap}(v,T,\ell)\geq\frac{\operatorname{vol}(T)}{2m}+\frac{77}{486}\cdot
n^{-1/5}$ will exist, for every $v\in P$. Also note that
$\operatorname{vol}(T)\leq\operatorname{vol}(S)\leq\operatorname{vol}(V)=2m$.
For some appropriate constant $c_{1}$, $\operatorname{vol}(T)=c_{1}\cdot
m=\Theta(m)$. Furthermore, let $Y_{u,T}$ be the number of walks that ended in
the set $T$ (corresponding to $u$ as in Corollary 11) after $\ell$ steps. It
follows that

$\mathbb{E}Y_{u,T}\geq
K\cdot\left(\frac{\operatorname{vol}(T)}{2m}+\frac{77}{486}n^{-1/5}\right)\geq
m\cdot\operatorname{vol}(T)+\frac{154}{486}\cdot\frac{m^{2}}{n^{1/5}}.$

Let $c_{2}=\frac{77}{486}$. Note that the random variable $Y_{u,T}$ is the sum
of $K$ Bernoulli trials each with success probability at least
$\operatorname{vol}(T)/2m+c_{2}\cdot n^{-1/5}$. By an application of Chernoff
bounds and using $\operatorname{vol}(T)\leq m$, we get

$\displaystyle\Pr\left[Y_{u,T}<\left(1-3(m\cdot\operatorname{vol}(T))^{-1/2}\right)\mathbb{E}[Y_{u,T}]\right]$
$\displaystyle\quad<\exp\left(-4(m\cdot\operatorname{vol}(T))^{-1}\cdot\mathbb{E}[Y_{u,T}]\right)$
$\displaystyle\quad\leq\exp\left(-4(m\cdot\operatorname{vol}(T))^{-1}\cdot\left(\operatorname{vol}(T)\cdot
m+2c_{2}m^{2}n^{-1/5}\right)\right)$
$\displaystyle\quad\leq\exp\left(-4\cdot(1+\Theta(n^{-1/5})\right)$
$\displaystyle\quad<\frac{1}{10}.$

It follows that, the total number of walks received by set $T$ is at least

$\displaystyle(1-3(m\cdot\operatorname{vol}(T))^{-1/2})\cdot\mathbb{E}[Y_{u,T}]$
$\displaystyle\quad\geq(1-3(m\cdot\operatorname{vol}(T))^{-1/2})\left(m\cdot\operatorname{vol}(T)+2c_{2}{m^{2}/n^{1/5}}\right)$
$\displaystyle\quad\geq
m\cdot\operatorname{vol}(T)+2c_{2}{m^{2}/n^{1/5}}-3\sqrt{m}\sqrt{\operatorname{vol}(T)}-6c_{2}m^{3/2}(\operatorname{vol}(T))^{-1/2}n^{-1/5}.$

with probability at least $9/10$.

Now, the number of walks received by any vertex $v\in T$ is minimum when the
walks within $T$ have mixed well and have reached their stationary
distribution with respect to set $T$, i.e, for any $v\in T$, the endpoint
distribution (restricted to set $T$) is
$\operatorname{deg}(v)/\operatorname{vol}(T)$. Therefore, it follows that the
number of walks received by a vertex $v\in T$ is at least

$\operatorname{deg}(v)\cdot\left(m+2c_{2}\frac{m^{2}}{n^{1/5}\cdot\operatorname{vol}(T)}-3\frac{\sqrt{m}\cdot\sqrt{\operatorname{vol}(T)}}{\operatorname{vol}(T)}-6c_{2}\frac{m^{3/2}}{(\operatorname{vol}(T))^{3/2}n^{1/5}}\right).$

Recalling that $\operatorname{vol}(T)=c_{1}m$, the expected number of walks
received by a vertex $v\in T$ of degree $\operatorname{deg}(v)$ is at least

$\operatorname{deg}(v)\cdot\left(m+2\frac{c_{2}}{c_{1}}\frac{m}{n^{1/5}}-\frac{3}{\sqrt{c_{1}}}-6\frac{c_{2}}{(c_{1})^{3/2}n^{-1/5}}\right)=\operatorname{deg}(v)\cdot\left(m+2\frac{c_{2}}{c_{1}}\frac{m}{n^{1/5}}-O(1)\right).$

Therefore, on an average vertex $v\in T$ of degree $\operatorname{deg}(v)$
receives more than the threshold
$\tau_{v}=m\cdot\operatorname{deg}(v)+2m\cdot\operatorname{deg}(v)/n^{1/4}$
number of walks for large enough $n$. Thus, some vertex in $T$ will receive
more than $\tau_{v}$ walks and it will output _Reject_.

Let $\mathcal{E}$ be the event that none of the vertices in $P$ is sampled to
be one of the starting points in $Q$. Since each vertex $u\in V$ is sampled
with probability $5000\cdot\frac{\operatorname{deg}(v)}{2\epsilon\cdot m}$ and
$\operatorname{vol}(P)\geq\frac{5\epsilon\cdot m}{4860}$, it follows that

$Pr[\mathcal{E}]\leq\left(1-5000\cdot\frac{\operatorname{deg}(v)}{2\epsilon\cdot
m}\right)^{\frac{5\epsilon\cdot m}{4860}}\leq e^{-2.5}=0.08.$

Taking a union bound over the probability of the event $\mathcal{E}$ and the
probability of set $T$ around a starting vertex $u\in P$ not receiving enough
walks, we get that with probability at most $0.1+0.08=0.18$, no vertex will
output _Reject_. Thus, our distributed algorithm will output _Reject_ with
probability at least $2/3$, on at least one vertex of $G$.

Finally, the upper bound on the number of communication rounds follows from
the length $\ell=\frac{32}{\alpha^{2}}\log n$ of each random walk. ∎

## References

  * [1] Noga Alon.  Eigenvalues and expanders, 1986.
  * [2] Noga Alon and V. D. Milman.  Eigenvalues, expanders and superconcentrators (extended abstract).  In 25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984, pages 320–322. IEEE Computer Society, 1984.  https://doi.org/10.1109/SFCS.1984.715931 doi:10.1109/SFCS.1984.715931.
  * [3] Zvika Brakerski and Boaz Patt-Shamir.  Distributed discovery of large near-cliques.  In Idit Keidar, editor, Distributed Computing, pages 206–220, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [4] Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, and Yadu Vasudev.  Fast Distributed Algorithms for Testing Graph Properties.  Distributed Computing, 32(1):41–57, Feb 2019.  https://doi.org/10.1007/s00446-018-0324-8 doi:10.1007/s00446-018-0324-8.
  * [5] Fan R. K. Chung.  Spectral Graph Theory.  Providence, RI, 1997.
  * [6] Artur Czumaj and Christian Sohler.  Testing Expansion in Bounded-Degree Graphs.  Combinatorics, Probability & Computing, 19(5-6):693–709, 2010\.  https://doi.org/10.1017/S096354831000012X doi:10.1017/S096354831000012X.
  * [7] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer.  Distributed verification and hardness of distributed approximation.  In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, page 363?372, New York, NY, USA, 2011. Association for Computing Machinery.  https://doi.org/10.1145/1993636.1993686 doi:10.1145/1993636.1993686.
  * [8] Jozef Dodziuk.  Difference equations, isoperimetric inequality and transience of certain random walks.  Transactions of the American Mathematical Society, 284(2):787–794, 1984.  URL: http://www.jstor.org/stable/1999107.
  * [9] 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 Andréa W. Richa, editor, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:30, Dagstuhl, Germany, 2017\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7984, https://doi.org/10.4230/LIPIcs.DISC.2017.15 doi:10.4230/LIPIcs.DISC.2017.15.
  * [10] Hendrik Fichtenberger and Yadu Vasudev.  A two-sided error distributed property tester for conductance.  In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 19:1–19:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  https://doi.org/10.4230/LIPIcs.MFCS.2018.19 doi:10.4230/LIPIcs.MFCS.2018.19.
  * [11] Orr Fischer, Tzlil Gonen, and Rotem Oshman.  Distributed Property Testing for Subgraph-Freeness Revisited.  CoRR, abs/1705.04033, 2017.  URL: http://arxiv.org/abs/1705.04033, http://arxiv.org/abs/1705.04033 arXiv:1705.04033.
  * [12] Shayan Oveis Gharan and Luca Trevisan.  Approximating the expansion profile and almost optimal local graph clustering.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 187–196. IEEE Computer Society, 2012.  https://doi.org/10.1109/FOCS.2012.85 doi:10.1109/FOCS.2012.85.
  * [13] O. Goldreich, S. Goldwasser, and D. Ron.  Property testing and its connection to learning and approximation.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 339–348, 1996.  https://doi.org/10.1109/SFCS.1996.548493 doi:10.1109/SFCS.1996.548493.
  * [14] Oded Goldreich.  Introduction to Testing Graph Properties, pages 105–141.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.  https://doi.org/10.1007/978-3-642-16367-8_7 doi:10.1007/978-3-642-16367-8_7.
  * [15] Oded Goldreich.  Introduction to Property Testing.  Cambridge University Press, 2017.  https://doi.org/10.1017/9781108135252 doi:10.1017/9781108135252.
  * [16] 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, page 406?415, New York, NY, USA, 1997. Association for Computing Machinery.  https://doi.org/10.1145/258533.258627 doi:10.1145/258533.258627.
  * [17] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  Electron. Colloquium Comput. Complex., (20), 2000.  URL: https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-020/index.html.
  * [18] Satyen Kale and C. Seshadhri.  An expansion tester for bounded degree graphs.  SIAM J. Comput., 40(3):709–720, 2011.  https://doi.org/10.1137/100802980 doi:10.1137/100802980.
  * [19] Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan.  Sublinear bounds for randomized leader election.  In Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Networking, pages 348–362, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * [20] Angsheng Li and Pan Peng.  Testing small set expansion in general graphs.  In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 622–635. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.  https://doi.org/10.4230/LIPIcs.STACS.2015.622 doi:10.4230/LIPIcs.STACS.2015.622.
  * [21] Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski.  Walking randomly, massively, and efficiently.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 364?377, New York, NY, USA, 2020. Association for Computing Machinery.  https://doi.org/10.1145/3357713.3384303 doi:10.1145/3357713.3384303.
  * [22] Asaf Nachmias and Asaf Shapira.  Testing the expansion of a graph.  Information and Computation, 208(4):309–314, 2010.  URL: https://www.sciencedirect.com/science/article/pii/S0890540109001801, https://doi.org/https://doi.org/10.1016/j.ic.2009.09.002 doi:https://doi.org/10.1016/j.ic.2009.09.002.
  * [23] David Peleg.  Distributed Computing: A Locality-Sensitive Approach.  Society for Industrial and Applied Mathematics, 2000.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9780898719772, http://arxiv.org/abs/https://epubs.siam.org/doi/pdf/10.1137/1.9780898719772 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9780898719772, https://doi.org/10.1137/1.9780898719772 doi:10.1137/1.9780898719772.
  * [24] Seth Pettie and Hsin-Hao Su.  Distributed coloring algorithms for triangle-free graphs.  Inf. Comput., 243(C):263?280, aug 2015.  https://doi.org/10.1016/j.ic.2014.12.018 doi:10.1016/j.ic.2014.12.018.
  * [25] Alistair Sinclair.  Algorithms for Random Generation and Counting: A Markov Chain Approach.  Birkhauser Verlag, CHE, 1993.