Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR07-118 | 27th November 2007 00:00

Testing the Expansion of a Graph

TR07-118
Authors: Asaf Nachmias, Asaf Shapira
Publication: 28th November 2007 09:53
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint