×

zbMATH — the first resource for mathematics

Basic facts about expander graphs. (English) Zbl 1343.68182
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, 451-464 (2011).
Summary: In this survey we review basic facts regarding expander graphs that are most relevant to the theory of computation.
For the entire collection see [Zbl 1220.68005].

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C75 Structural characterization of families of graphs
05C81 Random walks on graphs
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ajtai, M., Komlos, J., Szemerédi, E.: An O(nlogn) Sorting Network. In: 15th STOC, pp. 1–9 (1983)
[2] Ajtai, M., Komlos, J., Szemerédi, E.: Deterministic Simulation in LogSpace. In: 19th STOC, pp. 132–140 (1987)
[3] Alon, N.: Eigenvalues and expanders. Combinatorica 6, 83–96 (1986) · Zbl 0661.05053
[4] Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.: Construction of Asymptotically Good, Low-Rate Error-Correcting Codes through Pseudo-Random Graphs. IEEE Transactions on Information Theory 38, 509–516 (1992) · Zbl 0744.94023
[5] Alon, N., Milman, V.D.: {\(\lambda\)} 1, Isoperimetric Inequalities for Graphs and Superconcentrators, J. J. Combinatorial Theory, Ser. B 38, 73–88 (1985) · Zbl 0549.05051
[6] Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. John Wiley & Sons, Chichester (1992, 2000) · Zbl 0767.05001
[7] Gabber, O., Galil, Z.: Explicit Constructions of Linear Size Superconcentrators. JCSS 22, 407–420 (1981) · Zbl 0487.05045
[8] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056
[9] Healy, A.: Randomness-efficient sampling within NC1. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol. 4110, pp. 398–409. Springer, Heidelberg (2006) · Zbl 1155.68391
[10] Hoory, S., Linial, N., Wigderson, A.: Expander Graphs and their Applications. Bull. AMS 43(4), 439–561 (2006) · Zbl 1147.68608
[11] Impagliazzo, R., Kabanets, V.: Constructive Proofs of Concentration Bounds. In: ECCC, TR10-072 (2010) · Zbl 1305.68331
[12] Kahale, N.: Eigenvalues and Expansion of Regular Graphs. JACM 42(5), 1091–1106 (1995) · Zbl 0885.68117
[13] Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan Graphs. Combinatorica 8, 261–277 (1988) · Zbl 0661.05035
[14] Margulis, G.A.: Explicit Construction of Concentrators. Prob. Per. Infor. 9(4), 325–332 (1975) (in Russian); English translation in Problems of Infor. Trans. pp. 325–332 (1975)
[15] Reingold, O.: Undirected ST-Connectivity in Log-Space. In: 37th STOC, pp. 376–385 (2005) · Zbl 1192.68374
[16] Reingold, O., Vadhan, S., Wigderson, A.: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Annals of Mathematics 155(1), 157–187 (2001); Preliminary version in 41st FOCS, pp. 3–13 (2000) · Zbl 1008.05101
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.