TR07-118 Authors: Asaf Nachmias, Asaf Shapira

Publication: 28th November 2007 09:53

Downloads: 1452

Keywords:

We study the problem of testing the expansion of

graphs with bounded degree d in sublinear time. A graph is said to

be an \alpha-expander if every vertex set U \subset V of size at

most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm proposed by Goldreich and Ron (ECCC-2000)

for testing the expansion of a graph distinguishes with high

probability between \alpha-expanders of degree bound d and

graphs which are \eps-far from having expansion at least

\Omega(\alpha^2). This improves a recent result of Czumaj and

Sohler (FOCS-2007) who showed that this algorithm can distinguish

between \alpha-expanders of degree bound d and graphs which are

\eps-far from having expansion at least \Omega(\alpha^2/\log n).

It also improves a recent result of Kale and Seshadhri

(ECCC-2007) who showed that this algorithm can distinguish between

\alpha-expanders and graphs which are \eps-far from having

expansion at least \Omega(\alpha^2) with twice the maximum degree.

Finally, our result shows that the conjecture of Goldreich and Ron, on testing the second eigenvalue of the graph, holds when

the second eigenvalue lies in a certain interval of constant size.

Our methods combine the techniques of the above three papers.