Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-789-07
Testing Expansion in Bounded Degree Graphs
Authors: Kale, Satyen, Seshadhri, C.
Date:July 2007
Pages:7
Download Formats: [PDF]
Abstract:
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}{epsilonalpha2})$ for any given constant $mu > 0$.