Expander graphs and their applications. (English) Zbl 1147.68608

Hoory, Shlomo; Linial, Nathan; Widgerson, Avi

Bull. Am. Math. Soc., New Ser. 43, No. 4, 439-561 (2006).

From the text: A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in numerous and often surprising contexts in both fields. ...
Expander graphs were first defined by L. A. Bassalygo and M. S. Pinsker [Probl. Inf. Transm. 9, 64–66 (1974); translation from Probl. Peredachi Inf. 9, No. 1, 84–87 (1973; Zbl 0327.94051)], and their existence first proved by Pinsker in the early 1970s [On the complexity of a concentrator. In: Proc. 7th Int. Teletraffic Conference, Stockholm 1973, 318/1–318/4 (1973)]. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. It is not surprising that expanders are useful in the design and analysis of communication networks. What is less obvious is that expanders have surprising utility in other computational settings such as in the theory of error correcting codes and the theory of pseudorandomness.
In mathematics, we will encounter e.g. their role in the study of metric embeddings, and in particular in work around the Baum-Connes Conjecture. Expansion is closely related to the convergence rates of Markov chains, and so they play a key role in the study of Monte-Carlo algorithms in statistical mechanics and in a host of practical computational applications. The list of such interesting and fruitful connections goes on and on with so many applications we will not even be able to mention. This universality of expanders is becoming more evident as more connections are discovered. It transpires that expansion is a fundamental mathematical concept, well deserving to be thoroughly investigated on its own.
In hindsight, one reason that expanders are so ubiquitous is that their very definition can be given in at least three languages: combinatorial/geometric, probabilistic and algebraic. Combinatorially, expanders are graphs which are highly connected; to disconnect a large part of the graph, one has to sever many edges. Equivalently, using the geometric notion of isoperimetry, every set of vertices has a (relatively) very large boundary. From the probabilistic viewpoint, one considers the natural random walk on a graph, in which we have a token on a vertex, that moves at every step to a random neighboring vertex, chosen uniformly and independently. Expanders are graphs for which this process converges to its limiting distribution as rapidly as possible. Algebraically, one can consider the Laplace operator on the graph and its spectrum. From this perspective, expanders are graphs in which the first positive eigenvalue (of their Laplace operator) is bounded away from zero.
The study of expanders leads in different directions. There are structural problems: what are the best bounds on the various expansion parameters, and how do they relate to each other and to other graph invariants? There are problems concerning explicit constructions: how to efficiently generate expanders with given parameters. These are extremely important for applications. There are algorithmic problems – given a graph, test if it is an expander with given parameters. Finally, there is the problem of understanding the relation of expansion with other mathematical notions, and the application of expanders to practical and theoretical problems.
In the past four decades, a great amount of research has been done on these topics, resulting in a wide-ranging body of knowledge. In this survey, we could not hope to cover even a fraction of it. We have tried to make the presentation as broad as possible, touching on the various research directions mentioned above. Even what we do cover is of course incomplete, and we try to give the relevant references for more comprehensive coverage. We have also tried to mention in each section related research which we are not covering at all and to reference some of this as well.
The selection of material naturally reflects our interests and biases. It is rather diverse and can be read in different orders, according to the reader’s taste and interests.
General background material on the computer science side includes the books on Computational Complexity (specifically, complexity classes) [C. H. Papadmitriou, Computational complexity. Amsterdam: Addison-Wesley Publishing Company (1994; Zbl 0833.68049), M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company (1997)], on Algorithms [T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms. 2nd ed. Cambridge, MA: MIT Press (2001; Zbl 1047.68161)] and on Randomized Algorithms [R. Motwani and P. Raghavan, Randomized algorithms. Cambridge: Cambridge Univ. Press (1995; Zbl 0849.68039)], and the survey on the P versus NP problem [A. Wigderson, in: Sanz-Solé, Marta (ed.) et al., Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22–30, 2006. Volume I. Zürich: European Mathematical Society (EMS), 665–712 (2007; Zbl 1149.68033)].
This article evolved from lecture notes for a course on expanders taught at the Hebrew University, Israel, in 2003 by Nati Linial and Avi Wigderson.
Contents:
1. The magical mystery tour: Three motivating problems: Hardness results for linear transformations, Construction of good error correcting codes, Deterministic error amplification for RP; Magical graphs; The three solutions: A super concentrator with \(O(n)\) edges, Construction of good error correcting codes, Deterministic error amplification for RP.
2. Graph expansion and eigenvalues: Edge expansion and a combinatorial definition of expanders; Examples of expander graphs; Graph spectrum and an algebraic definition of expansion; The Expander Mixing Lemma; How big can the spectral gap be? Four perspectives on expansion and how they compare: Extremal problems, Typical behavior, Explicit constructions, Algorithms, Comparisons.
3. Random walks on expander graphs: Rapid mixing of walk: Convergence in the \(l_1\) and \(l_2\) norms, Convergence in entropy; Random walks resemble independent sampling; Applications: Efficient error reduction in probabilistic algorithms, Hardness of approximating maximum clique size.
4. A geometric view of expander graphs: The classical isoperimetric problem; Graph isoperimetric problems, Example: The discrete cube; The Margulis construction: The discrete Laplacian; The Cheeger constant and inequality; Expansion and the spectral gap: Large spectral gap implies high expansion, High expansion implies large spectral gap; Expansion of small sets: Connection with the spectral gap, Typical behavior; Expansion in hypergraphs?.
5. Extremal problems on spectrum and expansion: The d-regular tree: The expansion of \(T_d\), The spectrum of \(T_d\); The Alon-Boppana lower bound: Statement of the theorem, Proof I: Counting closed walks in \(T_d\), Proof II: Using spherical functions; Extensions of the Alon-Boppana theorem; Ramanujan graphs.
6. Spectrum and expansion in lifts of graphs: Covering maps and lifts; Eigenvalues – old and new; The universal covering tree: Irregular Ramanujan graphs? Nearly-Ramanujan graphs by way of 2-lifts.
7. The spectrum of random graphs: The bulk of the spectrum; The extreme eigenvalues: An illustration of the trace method; Variations on a theme: Back to the irregular case, Are most regular graphs Ramanujan?, More on random lifts,The eigenvectors.
8. The Margulis construction: A detour into harmonic analysis: Characters; Back to the proof.
9. The zig-zag product: Introduction; Construction of an expander family using zig-zag; Definition and analysis of the zig-zag product; Entropy analysis; An application to complexity theory: SL \(=\) L.
10. Lossless conductors and expanders: Conductors and lossless expanders; Conductors; Lossless expanders; The construction; The zig-zag product for conductors; Proof of the main theorem; Final comments.
11. Cayley expander graphs: Representations of finite groups; Representations and irreducible representations; Schreier graphs; Kazhdan constant and expansion of Cayley graphs; The replacement product and semidirect product; Constructing expander families by iterated semidirect products; Cayley expanders from group rings; Cayley expanders from iterated wreath products; Expansion is not a group property; Hypercontractive inequalities in groups.
12. Error correcting codes: Definition of error correcting codes; Linear code; Asymptotic bounds; Lower bounds on size: The Gilbert-Varshamov bound; Upper bounds: Sphere packing and linear programming; Codes from graphs; Efficient asymptotically good codes from lossless expanders.
13. Metric embedding: Basic definitions; Finding the minimal \(l_2\) distortion; Distortion bounds via semidefinite duality; Embedding the cube into \(l_2\); Embedding expander graphs into l2; Algorithms for cut problems via embeddings; A glimpse into the bigger picture.

Reviewer: Olaf Ninnemann (Uffing am Staffelsee)

MSC:

68R10	Graph theory (including graph drawing) in computer science
68-02	Research exposition (monographs, survey articles) pertaining to computer science
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94B05	Linear codes (general theory)
05C25	Graphs and abstract algebra (groups, rings, fields, etc.)
05C80	Random graphs (graph-theoretic aspects)

Citations:

Zbl 0327.94051; Zbl 0833.68049; Zbl 1047.68161; Zbl 0849.68039; Zbl 1149.68033

References:

[1]	N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38(2):509-516, 1992. · Zbl 0744.94023
[2]	Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson, Pseudorandom generators in propositional proof complexity, SIAM J. Comput. 34 (2004), no. 1, 67 – 88. · Zbl 1096.03070
[3]	N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 1988, pp. 15 – 19. · Zbl 0657.05068
[4]	N. Alon and M. Capalbo. Explicit unique-neighbor expanders. In 43nd IEEE Symposium on Foundations of Computer Science (Vancouver, BC), pages 73-79. IEEE Computer Society, 2002.
[5]	N. Alon and M. Capalbo, Smaller explicit superconcentrators, Internet Math. 1 (2004), no. 2, 151 – 163. · Zbl 1063.68075
[6]	O. Angel, J. Friedman, and S. Hoory. The non-backtracking spectrum of the universal cover of a graph. Manuscript. · Zbl 1310.05136
[7]	Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman, Derandomized graph products, Comput. Complexity 5 (1995), no. 1, 60 – 75. · Zbl 0816.60070
[8]	Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) IEEE, New York, 1979, pp. 218 – 223.
[9]	M. Ajtai, J. Komlós, and E. Szemerédi. An \( O(n\log n)\) sorting network. Combinatorica, 3(1):1-19, 1983.
[10]	M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 132-140, 1987.
[11]	Alon Amit and Nathan Linial, Random lifts of graphs: edge expansion, Combin. Probab. Comput. 15 (2006), no. 3, 317 – 332. · Zbl 1095.05034
[12]	S. Arora and C. Lund. Hardness of approximations. In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston, MA, 1996.
[13]	Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1 – 18. · Zbl 0996.05105
[14]	Sanjeev Arora, F. T. Leighton, and Bruce M. Maggs, On-line algorithms for path selection in a nonblocking network, SIAM J. Comput. 25 (1996), no. 3, 600 – 625. · Zbl 0852.68004
[15]	Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70 – 122. , https://doi.org/10.1145/273865.273901 Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, Proof verification and the hardness of approximation problems, J. ACM 45 (1998), no. 3, 501 – 555. · Zbl 1065.68570
[16]	Alon Amit, Nathan Linial, and Jiří Matoušek, Random lifts of graphs: independence and chromatic number, Random Structures Algorithms 20 (2002), no. 1, 1 – 22. · Zbl 0993.05071
[17]	N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83 – 96. Theory of computing (Singer Island, Fla., 1984). · Zbl 0661.05053
[18]	Noga Alon, On the edge-expansion of graphs, Combin. Probab. Comput. 6 (1997), no. 2, 145 – 152. · Zbl 0881.05077
[19]	Noga Alon, Alexander Lubotzky, and Avi Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 630 – 637.
[20]	N. Alon and V. D. Milman, \?\(_{1}\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73 – 88. · Zbl 0549.05051
[21]	Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271 – 284. · Zbl 0798.05048
[22]	Michael Alekhnovich and Alexander A. Razborov, Lower bounds for polynomial calculus: non-binomial case, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 190 – 199.
[23]	Sanjeev Arora, Satish Rao, and Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 222 – 231. · Zbl 1192.68467
[24]	Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70 – 122. , https://doi.org/10.1145/273865.273901 Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, Proof verification and the hardness of approximation problems, J. ACM 45 (1998), no. 3, 501 – 555. · Zbl 1065.68570
[25]	Noga Alon and Joel H. Spencer, The probabilistic method, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. With an appendix on the life and work of Paul Erdős. · Zbl 0996.05001
[26]	B. Brinkman and M. Charikar. On the impossibility of dimension reduction in \( l_1\). In 44nd IEEE Symposium on Foundations of Computer Science (Cambridge, MA), pages 514-523. IEEE Computer Society, 2003.
[27]	K. Burgin, P. Chebolu, C. Cooper, and A.M. Frieze. Hamilton cycles in random lifts of graphs. Preprint at http://www.math.cmu.edu/  af1p/papers.html, 2005. · Zbl 1106.05087
[28]	William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159 – 182. · Zbl 0338.42017
[29]	Andrei Z. Broder, Alan M. Frieze, and Eli Upfal, Static and dynamic path selection on expander graphs: a random walk approach, Random Structures Algorithms 14 (1999), no. 1, 87 – 109. , https://doi.org/10.1002/(SICI)1098-2418(1999010)14:13.0.CO;2-O · Zbl 0963.68155
[30]	Yonatan Bilu and Shlomo Hoory, On codes from hypergraphs, European J. Combin. 25 (2004), no. 3, 339 – 354. · Zbl 1063.94104
[31]	M. Blum, R. M. Karp, O. Vornberger, C. H. Papadimitriou, and M. Yannakakis, The complexity of testing whether a graph is a superconcentrator, Inform. Process. Lett. 13 (1981), no. 4-5, 164 – 167. · Zbl 0482.05059
[32]	Y. Bilu and N. Linial. Lifts, discrepancy and nearly optimal spectral gaps. Combinatorica, to appear. · Zbl 1121.05054
[33]	H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh, Are bitvectors optimal?, SIAM J. Comput. 31 (2002), no. 6, 1723 – 1744. · Zbl 1008.68038
[34]	J. Buresh-Oppenheim, N. Galesi, S. Hoory, A. Magen, and T. Pitassi. Rank bounds and integrality gaps for cutting planes procedures. In 44nd IEEE Symposium on Foundations of Computer Science (Cambridge, MA, 2003), pages 318-327. IEEE Computer Society, 2003. · Zbl 1213.68328
[35]	Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986. Set systems, hypergraphs, families of vectors and combinatorial probability. · Zbl 0595.05001
[36]	Aline Bonami, Étude des coefficients de Fourier des fonctions de \?^{\?}(\?), Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 2, 335 – 402 (1971) (French, with English summary). · Zbl 0195.42501
[37]	J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46 – 52. · Zbl 0657.46013
[38]	L. A. Bassalygo and M. S. Pinsker, The complexity of an optimal non-blocking commutation scheme without reorganization, Problemy Peredači Informacii 9 (1973), no. 1, 84 – 87 (Russian). · Zbl 0327.94051
[39]	A. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In The 28th Annual Symposium on Foundations of Computer Science, pages 286-294, 1987.
[40]	Piotr Berman and Georg Schnitger, On the complexity of approximating the independent set problem, Inform. and Comput. 96 (1992), no. 1, 77 – 94. · Zbl 0804.90121
[41]	Eli Ben-Sasson and Avi Wigderson, Short proofs are narrow — resolution made simple, J. ACM 48 (2001), no. 2, 149 – 169. · Zbl 1089.03507
[42]	Peter Buser, A note on the isoperimetric constant, Ann. Sci. École Norm. Sup. (4) 15 (1982), no. 2, 213 – 230. · Zbl 0501.53030
[43]	Yu. D. Burago and V. A. Zalgaller, Geometric inequalities, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 285, Springer-Verlag, Berlin, 1988. Translated from the Russian by A. B. Sosinskiĭ; Springer Series in Soviet Mathematics. · Zbl 0633.53002
[44]	P. J. Cameron. A Markov chain for Steiner triple systems. Manuscript.
[45]	P. Cartier, Fonctions harmoniques sur un arbre, Symposia Mathematica, Vol. IX (Convegno di Calcolo delle Probabilità, INDAM, Rome, 1971) Academic Press, London, 1972, pp. 203 – 270 (French).
[46]	Jeff Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969) Princeton Univ. Press, Princeton, N. J., 1970, pp. 195 – 199.
[47]	Sebastian M. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory Ser. B 96 (2006), no. 3, 367 – 373. · Zbl 1137.05042
[48]	S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. In IEEE Conference on Computational Complexity, 2005. · Zbl 1132.68418
[49]	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. · Zbl 1047.68161
[50]	Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 659 – 668. · Zbl 1192.68475
[51]	James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297 – 301. · Zbl 0127.09002
[52]	D. Dolev, C. Dwork, N. Pippenger, and A. Wigderson. Superconcentrators, generalizers and generalized connectors with limited depth. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pages 42-51, 1983.
[53]	Reinhard Diestel, Graphentheorie, Springer-Lehrbuch. [Springer Textbook], Springer-Verlag, Berlin, 1996 (German). · Zbl 0957.05001
[54]	Y. Drier and N. Linial. Minors in lifts of graphs. Random Structures and Algorithms, to appear. · Zbl 1226.05235
[55]	Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. · Zbl 0885.52001
[56]	Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787 – 794. · Zbl 0512.39001
[57]	Giuliana Davidoff, Peter Sarnak, and Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. · Zbl 1032.11001
[58]	P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290 – 297. · Zbl 0092.15705
[59]	William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. · Zbl 0077.12201
[60]	U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost np-complete. In 32nd IEEE Symposium on Foundations of Computer Science, pages 2-12. IEEE Computer Society, 1991.
[61]	Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233 – 241. · Zbl 0494.15010
[62]	J. Friedman, J. Kahn, and E. Szemeredi. On the second eigenvalue of random regular graphs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 587-598, 1989.
[63]	J. Friedman. A proof of Alon’s second eigenvalue conjecture. Memoirs of the A.M.S., to appear. · Zbl 1192.05087
[64]	Joel Friedman, The spectra of infinite hypertrees, SIAM J. Comput. 20 (1991), no. 5, 951 – 961. · Zbl 0765.05068
[65]	Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487 – 525. · Zbl 0785.05066
[66]	Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19 – 35. · Zbl 1035.05058
[67]	Joel Friedman and Avi Wigderson, On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), no. 1, 43 – 65. · Zbl 0843.05075
[68]	R. G. Gallager, Low-density parity-check codes, IRE Trans. IT-8 (1962), 21 – 28. · Zbl 0107.11802
[69]	Ofer Gabber and Zvi Galil, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci. 22 (1981), no. 3, 407 – 420. Special issued dedicated to Michael Machtey. · Zbl 0487.05045
[70]	David Gillman, A Chernoff bound for random walks on expander graphs, SIAM J. Comput. 27 (1998), no. 4, 1203 – 1220. · Zbl 0911.60016
[71]	Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, 2nd ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. · Zbl 0837.05001
[72]	O. Goldreich. A sample of samplers - a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity (ECCC), 1997. http://www.eccc.uni-trier.de/eccc/. · Zbl 1343.68297
[73]	Andrew Granville, It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. (N.S.) 42 (2005), no. 1, 3 – 38. · Zbl 1110.11002
[74]	Y. Greenberg. On the Spectrum of Graphs and Their Universal Covering. PhD thesis, Hebrew University of Jerusalem, 1995 (in Hebrew).
[75]	Jonathan L. Gross, Every connected regular graph of even degree is a Schreier coset graph, J. Combinatorial Theory Ser. B 22 (1977), no. 3, 227 – 232. · Zbl 0369.05042
[76]	Mikhael Gromov, Filling Riemannian manifolds, J. Differential Geom. 18 (1983), no. 1, 1 – 147. · Zbl 0515.53037
[77]	M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73 – 146. , https://doi.org/10.1007/s000390300002 L. Silberman, Addendum to: ”Random walk in random groups” [Geom. Funct. Anal. 13 (2003), no. 1, 73 – 146; MR1978492] by M. Gromov, Geom. Funct. Anal. 13 (2003), no. 1, 147 – 177. · Zbl 1124.20027
[78]	Johan Håstad, Clique is hard to approximate within \?^{1-\?}, Acta Math. 182 (1999), no. 1, 105 – 142. · Zbl 0989.68060
[79]	R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J. 29 (1950), 147 – 160.
[80]	S. Hoory, A. Magen, and T. Pitassi. Monotone circuits for the majority function. 10th International Workshop on Randomization and Computation (RANDOM), 2006. · Zbl 1155.68572
[81]	S. Hoory. On graphs of high girth. PhD thesis, Hebrew University of Jerusalem, 2002. · Zbl 1027.05050
[82]	Shlomo Hoory, A lower bound on the spectral radius of the universal cover of a graph, J. Combin. Theory Ser. B 93 (2005), no. 1, 33 – 43. · Zbl 1063.05091
[83]	P. Indyk and J. Matoušek. Low-distortion embeddings of finite metric spaces. In Jacob E. Goodman and Joseph O’Rourke, editors, Handbook of discrete and computational geometry, Discrete Mathematics and Its Applications (Boca Raton), pages 177-196. Chapman & Hall/CRC, Boca Raton, FL, second edition, 2004.
[84]	R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 356-364, 1994. · Zbl 1345.68269
[85]	Mark Jerrum, Counting, sampling and integrating: algorithms and complexity, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2003. · Zbl 1011.05001
[86]	William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189 – 206. · Zbl 0539.46017
[87]	Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. · Zbl 0968.05003
[88]	S. Jimbo and A. Maruoka, Expanders obtained from affine transformations, Combinatorica 7 (1987), no. 4, 343 – 355. · Zbl 0637.05017
[89]	Alistair Sinclair and Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93 – 133. · Zbl 0668.05060
[90]	M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, MA, 1996.
[91]	Mark Jerrum, Alistair Sinclair, and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004), no. 4, 671 – 697. · Zbl 1204.65044
[92]	Nabil Kahale, Eigenvalues and expansion of regular graphs, J. Assoc. Comput. Mach. 42 (1995), no. 5, 1091 – 1106. · Zbl 0885.68117
[93]	Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85 – 103.
[94]	Martin Kassabov, Kazhdan constants for \?\?_{\?}(\Bbb Z), Internat. J. Algebra Comput. 15 (2005), no. 5-6, 971 – 995. · Zbl 1097.22007
[95]	M. Kassabov. Symmetric groups and expander graphs. http://www.arxiv.org/abs/ math.GR/0505624, 2005. · Zbl 1191.20002
[96]	D. A. Kazhdan. On a connection between the dual space of a group and the structure of its closed subgroups. Func. Anal. Appl., 1:63-65, 1967. · Zbl 0168.27602
[97]	J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In 29th IEEE Symposium on Foundations of Computer Science (White Planes), pages 68-80. IEEE Computer Society, 1988.
[98]	M. Kassabov, A. Lubotzky, and N. Nikolov. Finite simple groups as expanders. http://www.arxiv.org/abs/math.GR/0510562, 2005. · Zbl 1161.20010
[99]	T. W. Körner, Fourier analysis, 2nd ed., Cambridge University Press, Cambridge, 1989. · Zbl 0649.42001
[100]	R. Karp, N. Pippenger, and M. Sipser. A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity, 1985.
[101]	S. Khot and N. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l1. In The 46th Annual Symposium on Foundations of Computer Science, 2005.
[102]	Nathan Linial, Finite metric-spaces — combinatorics, geometry and algorithms, Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 573 – 586. · Zbl 0997.05019
[103]	Nathan Linial and Eran London, On the expansion rate of Margulis expanders, J. Combin. Theory Ser. B 96 (2006), no. 3, 436 – 442. · Zbl 1089.05071
[104]	Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215 – 245. · Zbl 0827.05021
[105]	Nathan Linial and Avner Magen, Least-distortion Euclidean embeddings of graphs: products of cycles and expanders, J. Combin. Theory Ser. B 79 (2000), no. 2, 157 – 171. · Zbl 1026.05032
[106]	N. Linial, A. Magen, and A. Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002), no. 2, 380 – 394. · Zbl 0991.05037
[107]	Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, and Daniel A. Spielman, Improved low-density parity-check codes using irregular graphs, IEEE Trans. Inform. Theory 47 (2001), no. 2, 585 – 598. · Zbl 0999.94042
[108]	Alexander Lubotzky and Tatiana Nagnibeda, Not every uniform tree covers Ramanujan graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 202 – 212. · Zbl 1024.05021
[109]	J. R. Lee and A. Naor, Embedding the diamond graph in \?_{\?} and dimension reduction in \?\(_{1}\), Geom. Funct. Anal. 14 (2004), no. 4, 745 – 747. · Zbl 1069.46005
[110]	Satyanarayana V. Lokam, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, J. Comput. System Sci. 63 (2001), no. 3, 449 – 473. · Zbl 1006.68051
[111]	László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. · Zbl 0785.05001
[112]	A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261 – 277. · Zbl 0661.05035
[113]	Tom Leighton and Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), no. 6, 787 – 832. · Zbl 1065.68666
[114]	Nathan Linial and Eyal Rozenman, Random lifts of graphs: perfect matchings, Combinatorica 25 (2005), no. 4, 407 – 424. · Zbl 1091.05063
[115]	Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type \?_{\?}, European J. Combin. 26 (2005), no. 6, 965 – 993. · Zbl 1135.05038
[116]	A. Lubotzky. Finite simple groups of lie type as expanders. In preparation. · Zbl 1257.20016
[117]	Alexander Lubotzky, Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel, 1994. With an appendix by Jonathan D. Rogawski. · Zbl 0826.22012
[118]	A. Lubotzky and B. Weiss, Groups and expanders, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 95 – 109. · Zbl 0787.05049
[119]	László Lovász and Peter Winkler, Mixing times, Microsurveys in discrete probability (Princeton, NJ, 1997) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Amer. Math. Soc., Providence, RI, 1998, pp. 85 – 133. · Zbl 0908.60065
[120]	A. Lubotzky and A. Zuk. On property (t). In preparation.
[121]	G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71 – 80 (Russian). · Zbl 0312.22011
[122]	G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71 – 78. · Zbl 0492.05044
[123]	G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), no. 1, 51 – 60 (Russian); English transl., Problems Inform. Transmission 24 (1988), no. 1, 39 – 46.
[124]	Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. · Zbl 0999.52006
[125]	Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203 – 216. · Zbl 0468.05039
[126]	Moshe Morgenstern, Existence and explicit constructions of \?+1 regular Ramanujan graphs for every prime power \?, J. Combin. Theory Ser. B 62 (1994), no. 1, 44 – 62. · Zbl 0814.68098
[127]	Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. · Zbl 0849.68039
[128]	Russell A. Martin and Dana Randall, Sampling adsorbing staircase walks using a new Markov chain decomposition method, 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 492 – 502.
[129]	Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey Jr., and Lloyd R. Welch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Information Theory IT-23 (1977), no. 2, 157 – 166. · Zbl 0361.94016
[130]	F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library, Vol. 16. F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library, Vol. 16. · Zbl 0369.94008
[131]	F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library, Vol. 16. F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. North-Holland Mathematical Library, Vol. 16. · Zbl 0369.94008
[132]	Vitali D. Milman and Gideon Schechtman, Asymptotic theory of finite-dimensional normed spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. · Zbl 0606.46013
[133]	R. Montenegro and P. Tetali. A primer on modern techniques for bounding mixing times. Preprint at http://www.math.gatech.edu/ · Zbl 1193.68138
[134]	Roy Meshulam and Avi Wigderson, Expanders from symmetric codes, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 669 – 677. · Zbl 1192.68463
[135]	N. Nikolov. A product decomposition for the classical quasisimple groups. http://www.arxiv.org/abs/math.GR/0510173, 2005. · Zbl 1119.20025
[136]	A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207 – 210. · Zbl 0771.05064
[137]	A. Nilli, Tight estimates for eigenvalues of regular graphs, Electron. J. Combin. 11 (2004), no. 1, Note 9, 4. · Zbl 1053.05082
[138]	T. Novikoff. Asymptotic behavior of the random 3-regular bipartite graph. Preprint, 2002.
[139]	Noam Nisan and David Zuckerman, Randomness is linear in space, J. Comput. System Sci. 52 (1996), no. 1, 43 – 52. · Zbl 0846.68041
[140]	Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. · Zbl 0833.68049
[141]	M. S. Pinsker. On the complexity of a concentrator. In 7th International Telegraffic Conference, pages 318/1-318/4, 1973.
[142]	D. Peleg and E. Upfal, Constructing disjoint paths on expander graphs, Combinatorica 9 (1989), no. 3, 289 – 313. · Zbl 0686.68056
[143]	Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128 – 138. · Zbl 0426.10006
[144]	Omer Reingold, Undirected ST-connectivity in log-space, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 376 – 385. · Zbl 1192.68374
[145]	Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451 – 485. · Zbl 0854.20015
[146]	Ran Raz and Amir Shpilka, Lower bounds for matrix product in bounded depth circuits with arbitrary gates, SIAM J. Comput. 32 (2003), no. 2, 488 – 513. · Zbl 1029.68072
[147]	Thomas J. Richardson, M. Amin Shokrollahi, and Rüdiger L. Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans. Inform. Theory 47 (2001), no. 2, 619 – 637. · Zbl 1019.94034
[148]	Eyal Rozenman, Aner Shalev, and Avi Wigderson, A new family of Cayley expanders (?), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 445 – 454. · Zbl 1192.68862
[149]	O. Reingold, L. Trevisan, and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem. Technical Report TR05-022, Electronic Colloquium on Computational Complexity (ECCC), 2005. http://www.eccc.uni-trier.de/eccc/. · Zbl 1301.05317
[150]	T. Richardson and R. Urbanke. Modern coding theory. Draft of the book, http://lthcwww.epfl.ch/mct/index.php. · Zbl 1188.94001
[151]	Thomas J. Richardson and Rüdiger L. Urbanke, The capacity of low-density parity-check codes under message-passing decoding, IEEE Trans. Inform. Theory 47 (2001), no. 2, 599 – 618. · Zbl 1019.94033
[152]	Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. · Zbl 0867.46001
[153]	Eyal Rozenman and Salil Vadhan, Derandomized squaring of graphs, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 3624, Springer, Berlin, 2005, pp. 436 – 447. · Zbl 1142.05331
[154]	Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2) 155 (2002), no. 1, 157 – 187. · Zbl 1008.05101
[155]	Peter Sarnak, What is…an expander?, Notices Amer. Math. Soc. 51 (2004), no. 7, 762 – 763. · Zbl 1161.05341
[156]	Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott; Graduate Texts in Mathematics, Vol. 42. · Zbl 0355.20006
[157]	C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379 – 423, 623 – 656. · Zbl 1154.94303
[158]	Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145 – 168 (2001). · Zbl 0980.22017
[159]	G. Păun, G. Rozenberg, and A. Salomaa , Current trends in theoretical computer science, World Scientific Publishing Co., Inc., River Edge, NJ, 2004. The challenge of the new century; Vol. 1. Algorithms and complexity. · Zbl 1047.68163
[160]	A. Siegel. A historical review of the isoperimetric theorem in 2-d, and its place in elementary plane geometry. http://www.cs.nyu.edu/faculty/siegel/SCIAM.pdf.
[161]	Miklós Simonovits, How to compute the volume in high dimension?, Math. Program. 97 (2003), no. 1-2, Ser. B, 337 – 374. ISMP, 2003 (Copenhagen). · Zbl 1106.68433
[162]	M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. · Zbl 1169.68300
[163]	Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1723 – 1731. Codes and complexity. · Zbl 0943.94544
[164]	R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84 – 85. · Zbl 0345.10002
[165]	Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710 – 1722. Codes and complexity. · Zbl 0943.94543
[166]	H. Stark and A. Terras. Zeta functions of finite graphs and coverings, part iii. Advances in Mathematics, to appear. · Zbl 1207.05083
[167]	M. Sudan. A crash course on coding theory. http://theory.lcs.mit.edu/  madhu/coding/ibm/, 2000.
[168]	Madhu Sudan, Probabilistically checkable proofs, Computational complexity theory, IAS/Park City Math. Ser., vol. 10, Amer. Math. Soc., Providence, RI, 2004, pp. 349 – 389. · Zbl 1161.68021
[169]	R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533 – 547. · Zbl 0474.94029
[170]	R. Michael Tanner, Explicit concentrators from generalized \?-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287 – 293. · Zbl 0554.05045
[171]	J. Thorpe. Low-Density Parity-Check codes constructed from protographs. In The Interplanetary Network Progress Report 42-154, Jet Propulsion Laboratory, Pasadena, CA, pages 1-7, 2003.
[172]	Craig A. Tracy and Harold Widom, On orthogonal and symplectic matrix ensembles, Comm. Math. Phys. 177 (1996), no. 3, 727 – 754. · Zbl 0851.60101
[173]	Eli Upfal and Avi Wigderson, How to share memory in a distributed system, J. Assoc. Comput. Mach. 34 (1987), no. 1, 116 – 127. · Zbl 0629.68028
[174]	Leslie G. Valiant, Graph-theoretic properties in computational complexity, J. Comput. System Sci. 13 (1976), no. 3, 278 – 285. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975). · Zbl 0354.68071
[175]	Alain Valette, On the Baum-Connes assembly map for discrete groups, Proper group actions and the Baum-Connes conjecture, Adv. Courses Math. CRM Barcelona, Birkhäuser, Basel, 2003, pp. 79 – 124. With an appendix by Dan Kucerovsky.
[176]	J. H. van Lint, Introduction to coding theory, 3rd ed., Graduate Texts in Mathematics, vol. 86, Springer-Verlag, Berlin, 1999. · Zbl 0936.94014
[177]	J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd ed., Cambridge University Press, Cambridge, 2001. · Zbl 0980.05001
[178]	V. H. Vu, Spectral norm of random matrices, STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 423 – 430. · Zbl 1192.15017
[179]	Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325 – 327. · Zbl 0085.13203
[180]	A. Wigderson. P, NP and mathematics - a computational complexity perspective. In Proc. of the 2006 International Congress of Mathematicians. Madrid, August 2006. Preprint at http://www.math.ias.edu/  avi/PUBLICATIONS/MYPAPERS/W06/W06.pdf.
[181]	N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239 – 298. · Zbl 0935.05080
[182]	Avi Wigderson and David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Combinatorica 19 (1999), no. 1, 125 – 138. · Zbl 0929.05075
[183]	D. Zuckerman. Linear degree extractors and inapproximability of MAX-CLIQUE and chromatic number. Manuscript, 2005. · Zbl 1213.68322