文章基本信息

标题：On Testing Expansion in Bounded-Degree Graphs
本地全文：下载
作者：Oded Goldreich, Dana Ron
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 1, oracle access to a bounded-degree N-vertex graph, and two additional parameters 0 . The algorithm runs in time N05+\poly() , and accepts any graph having (normalized) second eigenvalue at most . We believe that the algorithm rejects any graph that is -far from having second eigenvalue at most O(1) , and prove the validity of this belief under an appealing combinatorial conjecture.
关键词：Eigenvalues, expansion, Graphs, Property Testing