Title: Distributed Testing of Conductance,
Abstract: We study the problem of testing conductance in the setting of distributed
computing and give a two-sided tester that takes $\mathcal{O}(\log(n) /
(\epsilon \Phi^2))$ rounds to decide if a graph has conductance at least $\Phi$
or is $\epsilon$-far from having conductance at least $\Phi^2 / 1000$ in the
distributed CONGEST model. We also show that $\Omega(\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.