ECCC-Report TR00-020https://eccc.weizmann.ac.il/report/2000/020Comments and Revisions published for TR00-020en-usTue, 28 Mar 2000 15:24:05 +0200
Paper TR00-020
| On Testing Expansion in Bounded-Degree Graphs |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2000/020
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.
Tue, 28 Mar 2000 15:24:05 +0200https://eccc.weizmann.ac.il/report/2000/020