TR00-020 Authors: Oded Goldreich, Dana Ron

Publication: 28th March 2000 15:24

Downloads: 2021

Keywords:

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed towards achieving the above

task. The algorithm is given a (normalized) second eigenvalue

bound $\lambda<1$, oracle access to a bounded-degree $N$-vertex graph,

and two additional parameters $\epsilon,\alpha>0$.

The algorithm runs in time $N^{0.5+\alpha}/\poly(\epsilon)$,

and accepts any graph having (normalized) second eigenvalue at most $\lambda$.

We believe that the algorithm rejects any graph that is $\epsilon$-far

from having second eigenvalue at most $\lambda^{\alpha/O(1)}$,

and prove the validity of this belief under an appealing

combinatorial conjecture.