×

On testing expansion in bounded-degree graphs. (English) Zbl 1343.68302

Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 68-75 (2011).
Summary: 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 foregoing task. The algorithm is given a (normalized) 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 }/\text{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.
For the entire collection see [Zbl 1220.68005].

MSC:

68W20 Randomized algorithms
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.: Eigenvalues and expanders. Combinatorica 6, 83–96 (1986) · Zbl 0661.05053 · doi:10.1007/BF02579166
[2] Alon, N., Milman, V.D.: {\(\lambda\)} 1, Isoperimetric Inequalities for Graphs and Superconcentrators. J. Combinatorial Theory, Ser. B 38, 73–88 (1985) · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[3] Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. John Wiley & Sons, Inc., Chichester (2000) · Zbl 0996.05001 · doi:10.1002/0471722154
[4] Batu, T., Fortnow, L., Rubinfeld, R., Smith, W.D., White, P.: Testing that Distributions are Close. In: 41st FOCS, pp. 259–269 (2000) · doi:10.1109/SFCS.2000.892113
[5] Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. In: Proc. of the 29th ACM Symp. on Theory of Computing, pp. 406–415 (1997) · Zbl 0963.68154 · doi:10.1145/258533.258627
[6] Goldreich, O., Ron, D.: A sublinear Bipartite Tester for Bounded Degree Graphs. Combinatorica 19(2), 1–39 (1999) · Zbl 0932.68053
[7] Goldreich, O., Sudan, M.: Computational Indistinguishability: A Sample Hierarchy. JCSS 59, 253–269 (1999)
[8] Kale, S., Seshadhri, C.: Testing expansion in bounded degree graphs. In: 35th ICALP, pp. 527–538 (2008); Preliminary version appeared as TR07-076, ECCC (2007) · Zbl 1153.68466
[9] Parnas, M., Ron, D.: Testing the diameter of graphs. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 85–96. Springer, Heidelberg (1999) · Zbl 0945.05057 · doi:10.1007/978-3-540-48413-4_9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.