Satyen Kale and C. Seshadhri
In SIAM Journal on Computing (SICOMP), 2011. Also appeared as ECCC Report TR07-131 and in proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008

We consider the problem of testing graph expansion (either vertex or edge) in the bounded degree model [Goldreich, Ron 2000]. 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 any graph with expansion \(\alpha’\) with degree bound \(d\), where \(\alpha’ < \alpha\) is a function of \(\alpha\). For edge expansion, we obtain \(\alpha’ = \Omega(\frac{\alpha^2}{d})\), and for vertex expansion, we obtain\(\alpha’ = \Omega(\frac{\alpha^2}{d^2})\). In either case, the algorithm runs in time \(\tilde{O}(\frac{n^{(1+\mu)/2}d^2}{\epsilon\alpha^2})\) for any given constant \(\mu > 0\).