Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an

expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and rejects it with high probability if it is $\epsilon$-far from a graph with expansion $\Omega(\alpha2)$. The algorithm runs in time $\tilde{O}(\frac{n^{0.5 + \mu}d2}{\epsilon\alpha2})$ for any given constant $\mu > 0$.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/310

[2] http://www.cs.princeton.edu/research/techreps/author/458

[3] ftp://ftp.cs.princeton.edu/techreports/2007/789.pdf