Testing Small Set Expansion in General Graphs

We consider the problem of testing small set expansion for general graphs. A graph G is a (k,phi)-expander if every subset of volume at most k has conductance at least phi. Small set expansion has recently received significant attention due to its close connection to the unique games conjecture, the local graph partitioning algorithms and locally testable codes. We give testers with two-sided error and one-sided error in the adjacency list model that allows degree and neighbor queries to the oracle of the input graph. The testers take as input an n-vertex graph G, a volume bound k, an expansion bound phi and a distance parameter varepsilon>0. For the two-sided error tester, with probability at least 2/3, it accepts the graph if it is a (k,phi)-expander and rejects the graph if it is varepsilon-far from any (k^*,phi^*)-expander, where k^*=Theta(kvarepsilon) and phi^*=Theta(frac{phi^4}{min{log(4m/k),log n}cdot(ln k)}). The query complexity and running time of the tester are widetilde{O}(sqrt{m}phi^{-4}varepsilon^{-2}), where m is the number of edges of the graph. For the one-sided error tester, it accepts every (k,phi)-expander, and with probability at least 2/3, rejects every graph that is varepsilon-far from (k^*,phi^*)-expander, where k^*=O(k^{1-xi}) and phi^*=O(xiphi^2) for any 0<xi