Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Expander graphs and their applications

Authors: Shlomo Hoory, Nathan Linial and Avi Wigderson
Journal: Bull. Amer. Math. Soc. 43 (2006), 439-561
MSC (2000): Primary 01-01, 68-01, 05-01, 68Q01, 94-01; Secondary 68Q15, 68Q17, 94B05, 05C25, 05C35, 05C40, 05C50, 05C80, 05C90, 60J10, 35J99, 20F05, 20F69, 20C99
Posted: August 7, 2006
MathSciNet review: 2247919
Full-text PDF

References

[ABN92] 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.
[ABSRW04] 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 (electronic), 10.1137/S0097539701389944. MR 2114305 (2006a:03078)
[AC89] 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, 10.1016/0012-365X(88)90189-6. MR 975519 (90f:05080)
[AC02] 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.
[AC04] N. Alon and M. Capalbo, Smaller explicit superconcentrators, Internet Math. 1 (2004), no. 2, 151–163. MR 2077222 (2006a:05140)
[AFH] O. Angel, J. Friedman, and S. Hoory.
The non-backtracking spectrum of the universal cover of a graph.
Manuscript.
[AFWZ95] Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman, Derandomized graph products, Comput. Complexity 5 (1995), no. 1, 60–75, 10.1007/BF01277956. MR 1319493 (95m:68082)
[AKL79] 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. MR 598110 (82h:68084)
[AKS83] M. Ajtai, J. Komlós, and E. Szemerédi. An $O(n\log n)$ sorting network. Combinatorica, 3(1):1-19, 1983.
[AKS87] 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.
[AL06] Alon Amit and Nathan Linial, Random lifts of graphs: edge expansion, Combin. Probab. Comput. 15 (2006), no. 3, 317–332, 10.1017/S0963548305007273. MR 2216470 (2007a:05125)
[AL96] 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.
[AL02] Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1–18, 10.1007/s004930200000. MR 1883559 (2003a:05131)
[ALM96] 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, 10.1137/S0097539791221499. MR 1390029 (97b:68014)
[ALM98] 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, 10.1145/278298.278306. MR 1639346 (99d:68077b)
[ALM02] 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, 10.1002/rsa.10003. MR 1871947 (2003a:05132)
[Alo86] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96, 10.1007/BF02579166. Theory of computing (Singer Island, Fla., 1984). MR 875835 (88e:05077)
[Alo97] Noga Alon, On the edge-expansion of graphs, Combin. Probab. Comput. 6 (1997), no. 2, 145–152, 10.1017/S096354839700299X. MR 1447810 (98c:05084)
[ALW01] 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. MR 1948752
[AM85] N. Alon and V. D. Milman, 𝜆₁, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88, 10.1016/0095-8956(85)90092-9. MR 782626 (87b:05092)
[AR94] Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284, 10.1002/rsa.3240050203. MR 1262979 (94k:05132)
[AR01] 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. MR 1948707
[ARV04] 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 (electronic), 10.1145/1007352.1007355. MR 2121604 (2005j:68081)
[AS98] Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122, 10.1145/273865.273901. MR 1614328 (99d:68077a)
[AS00] 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. MR 1885388 (2003f:60003)
[BC03] B. Brinkman and M. Charikar.
On the impossibility of dimension reduction in .
In 44nd IEEE Symposium on Foundations of Computer Science (Cambridge, MA), pages 514-523. IEEE Computer Society, 2003.
[BCCF05] 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.
[Bec75] William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 0385456 (52 #6317)
[BFU99] 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, 10.1002/(SICI)1098-2418(1999010)14:1<87::AID-RSA5>3.0.CO;2-O. MR 1662203 (99m:05144)
[BH04] Yonatan Bilu and Shlomo Hoory, On codes from hypergraphs, European J. Combin. 25 (2004), no. 3, 339–354, 10.1016/j.ejc.2003.10.002. MR 2036471 (2005d:94200)
[BKV81] 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, 10.1016/0020-0190(81)90050-8. MR 651465 (84f:68031)
[BL] Y. Bilu and N. Linial.
Lifts, discrepancy and nearly optimal spectral gaps.
Combinatorica, to appear.
[BMRV02] H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh, Are bitvectors optimal?, SIAM J. Comput. 31 (2002), no. 6, 1723–1744 (electronic), 10.1137/S0097539702405292. MR 1954872 (2004a:68014)
[BOGH03] 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.
[Bol86] Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986. Set systems, hypergraphs, families of vectors and combinatorial probability. MR 866142 (88g:05001)
[Bon70] 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). MR 0283496 (44 #727)
[Bou85] J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52, 10.1007/BF02776078. MR 815600 (87b:46017)
[BP73] 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). MR 0327387 (48 #5729)
[BS87] 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.
[BS92] Piotr Berman and Georg Schnitger, On the complexity of approximating the independent set problem, Inform. and Comput. 96 (1992), no. 1, 77–94, 10.1016/0890-5401(92)90056-L. MR 1142227 (92k:90110)
[BSW01] Eli Ben-Sasson and Avi Wigderson, Short proofs are narrow—resolution made simple, J. ACM 48 (2001), no. 2, 149–169, 10.1145/375827.375835. MR 1868713 (2002j:03066)
[Bus82] Peter Buser, A note on the isoperimetric constant, Ann. Sci. École Norm. Sup. (4) 15 (1982), no. 2, 213–230. MR 683635 (84e:58076)
[BZ88] 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. MR 936419 (89b:52020)
[Cam] P. J. Cameron.
A Markov chain for Steiner triple systems.
Manuscript.
[Car72] 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). MR 0353467 (50 #5950)
[Che70] 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. MR 0402831 (53 #6645)
[Cio06] Sebastian M. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory Ser. B 96 (2006), no. 3, 367–373, 10.1016/j.jctb.2005.09.002. MR 2220665 (2006m:05151)
[CKK05] 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.
[CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA, 2001. MR 1848805 (2002e:68001)
[CRVW02] 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 (electronic), 10.1145/509907.510003. MR 2121193
[CT65] James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 0178586 (31 #2843)
[DDPW83] 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.
[Die97] Reinhard Diestel, Graphentheorie, Springer-Lehrbuch. [Springer Textbook], Springer-Verlag, Berlin, 1996 (German). MR 1411445
[DL] Y. Drier and N. Linial.
Minors in lifts of graphs.
Random Structures and Algorithms, to appear.
[DL97] Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488 (98g:52001)
[Dod84] Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794, 10.1090/S0002-9947-1984-0743744-X. MR 743744 (85m:58185)
[DSV03] 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. MR 1989434 (2004f:11001)
[ER59] P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 0120167 (22 #10924)
[Fel68] William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons Inc., New York, 1968. MR 0228020 (37 #3604)
[FGL91] 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.
[FK81] Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241, 10.1007/BF02579329. MR 637828 (83e:15010)
[FKS89] 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.
[Fri] J. Friedman.
A proof of Alon's second eigenvalue conjecture.
Memoirs of the A.M.S., to appear.
[Fri91] Joel Friedman, The spectra of infinite hypertrees, SIAM J. Comput. 20 (1991), no. 5, 951–961, 10.1137/0220058. MR 1115660 (92k:05096)
[Fri93] Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487–525, 10.1215/S0012-7094-93-06921-9. MR 1208809 (94b:05134)
[Fri03] Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19–35, 10.1215/S0012-7094-03-11812-8. MR 1978881 (2004m:05165)
[FW95] Joel Friedman and Avi Wigderson, On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), no. 1, 43–65, 10.1007/BF01294459. MR 1325271 (96b:05110)
[Gal63] R. G. Gallager, Low-density parity-check codes, IRE Trans. IT-8 (1962), 21–28. MR 0136009 (24 #B2048)
[GG81] Ofer Gabber and Zvi Galil, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci. 22 (1981), no. 3, 407–420, 10.1016/0022-0000(81)90040-4. Special issued dedicated to Michael Machtey. MR 633542 (83d:94029)
[Gil98] David Gillman, A Chernoff bound for random walks on expander graphs, SIAM J. Comput. 27 (1998), no. 4, 1203–1220, 10.1137/S0097539794268765. MR 1621958 (99e:60076)
[GLS93] 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. MR 1261419 (95e:90001)
[Gol97] 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/.
[Gra05] 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 (electronic), 10.1090/S0273-0979-04-01037-7. MR 2115065 (2005k:11011)
[Gre95] Y. Greenberg.
On the Spectrum of Graphs and Their Universal Covering.
PhD thesis, Hebrew University of Jerusalem, 1995
(in Hebrew).
[Gro77] 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. MR 0450121 (56 #8419)
[Gro83] Mikhael Gromov, Filling Riemannian manifolds, J. Differential Geom. 18 (1983), no. 1, 1–147. MR 697984 (85h:53029)
[Gro03] M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146, 10.1007/s000390300002. MR 1978492 (2004j:20088a)
[Hås99] Johan Håstad, Clique is hard to approximate within 𝑛^{1-𝜀}, Acta Math. 182 (1999), no. 1, 105–142, 10.1007/BF02392825. MR 1687331 (2000j:68062)
[H50] R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J. 29 (1950), 147–160. MR 0035935 (12,35c)
[HMP06] S. Hoory, A. Magen, and T. Pitassi.
Monotone circuits for the majority function. 10th International Workshop on Randomization and Computation (RANDOM), 2006.
[Hoo02] S. Hoory.
On graphs of high girth.
PhD thesis, Hebrew University of Jerusalem, 2002.
[Hoo05] 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, 10.1016/j.jctb.2004.06.001. MR 2102266 (2005k:05144)
[IM04] 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.
[INW94] 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.
[Jer03] Mark Jerrum, Counting, sampling and integrating: algorithms and complexity, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2003. MR 1960003 (2004a:68044)
[JL84] 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. MR 737400 (86a:46018)
[J $\L$ R00] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847 (2001k:05180)
[JM87] S. Jimbo and A. Maruoka, Expanders obtained from affine transformations, Combinatorica 7 (1987), no. 4, 343–355, 10.1007/BF02579322. MR 931192 (89d:68071)
[JS89] Alistair Sinclair and Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and Comput. 82 (1989), no. 1, 93–133. MR 1003059 (91g:68084)
[JS96] 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.
[JSV04] 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 (electronic), 10.1145/1008731.1008738. MR 2147852 (2006b:15013)
[Kah95] Nabil Kahale, Eigenvalues and expansion of regular graphs, J. Assoc. Comput. Mach. 42 (1995), no. 5, 1091–1106, 10.1145/210118.210136. MR 1412045 (97f:68149)
[Kar72] 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. MR 0378476 (51 #14644)
[Kas05a] Martin Kassabov, Kazhdan constants for 𝑆𝐿_{𝑛}(\𝐵𝑏𝑏𝑍), Internat. J. Algebra Comput. 15 (2005), no. 5-6, 971–995, 10.1142/S0218196705002712. MR 2197816 (2007f:22012)
[Kas05b] M. Kassabov.
Symmetric groups and expander graphs. http://www.arxiv.org/abs/ math.GR/0505624, 2005.
[Kaz67] 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.
[KKL88] 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.
[KLN05] M. Kassabov, A. Lubotzky, and N. Nikolov.
Finite simple groups as expanders.
http://www.arxiv.org/abs/math.GR/0510562, 2005.
[Kör89] T. W. Körner, Fourier analysis, 2nd ed., Cambridge University Press, Cambridge, 1989. MR 1035216 (90j:42001)
[KPS85] R. Karp, N. Pippenger, and M. Sipser.
A time-randomness tradeoff.
In AMS Conference on Probabilistic Computational Complexity, 1985.
[KV05] 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.
[Lin02] Nathan Linial, Finite metric-spaces—combinatorics, geometry and algorithms, (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 573–586. MR 1957562 (2003k:05045)
[LL06] Nathan Linial and Eran London, On the expansion rate of Margulis expanders, J. Combin. Theory Ser. B 96 (2006), no. 3, 436–442, 10.1016/j.jctb.2005.09.001. MR 2220670 (2007a:05059)
[LLR95] Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245, 10.1007/BF01200757. MR 1337355 (96e:05158)
[LM00] 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, 10.1006/jctb.2000.1953. MR 1769197 (2002c:05062)
[LMN02] N. Linial, A. Magen, and A. Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002), no. 2, 380–394, 10.1007/s00039-002-8251-y. MR 1911665 (2003d:05054)
[LMSS01] 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, 10.1109/18.910576. MR 1820478 (2002h:94115)
[LN98] Alexander Lubotzky and Tatiana Nagnibeda, Not every uniform tree covers Ramanujan graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 202–212, 10.1006/jctb.1998.1843. MR 1654133 (2000g:05052)
[LN04] J. R. Lee and A. Naor, Embedding the diamond graph in 𝐿_{𝑝} and dimension reduction in 𝐿₁, Geom. Funct. Anal. 14 (2004), no. 4, 745–747, 10.1007/s00039-004-0473-8. MR 2084978 (2005g:46035)
[Lok01] 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, 10.1006/jcss.2001.1786. MR 1892859 (2003a:68059)
[Lov93] László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492 (94m:05001)
[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277, 10.1007/BF02126799. MR 963118 (89m:05099)
[LR99] 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, 10.1145/331524.331526. MR 1753034 (2001e:05125)
[LR05] Nathan Linial and Eyal Rozenman, Random lifts of graphs: perfect matchings, Combinatorica 25 (2005), no. 4, 407–424, 10.1007/s00493-005-0024-8. MR 2143247 (2006c:05110)
[LSV05] Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type 𝐴_{𝑑}, European J. Combin. 26 (2005), no. 6, 965–993, 10.1016/j.ejc.2004.06.007. MR 2143204 (2006g:20043)
[Lub] A. Lubotzky.
Finite simple groups of lie type as expanders.
In preparation.
[Lub94] 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. MR 1308046 (96g:22018)
[LW93] 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. MR 1235570 (95b:05097)
[LW98] 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. MR 1630411 (99h:60138)
[LZ] A. Lubotzky and A. Zuk.
On property (t).
In preparation.
[Mar73] G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767 (58 #4643)
[Mar82] G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71–78, 10.1007/BF02579283. MR 671147 (83j:05053)
[Mar88] 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. MR 939574 (89f:68054)
[Mat02] Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299 (2003f:52011)
[McK81] Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203–216, 10.1016/0024-3795(81)90150-6. MR 629617 (84h:05089)
[Mor94] 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, 10.1006/jctb.1994.1054. MR 1290630 (95h:05089)
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. MR 1344451 (96i:65003)
[MR00] 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, 10.1109/SFCS.2000.892137. MR 1931846
[MRRW77] 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. MR 0439403 (55 #12296)
[MS77a] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Publishing Co., Amsterdam, 1977. North-Holland Mathematical Library, Vol. 16. MR 0465509 (57 #5408a)
[MS77b] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. II, North-Holland Publishing Co., Amsterdam, 1977. North-Holland Mathematical Library, Vol. 16. MR 0465510 (57 #5408b)
[MS86] 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. MR 856576 (87m:46038)
[MT] R. Montenegro and P. Tetali.
A primer on modern techniques for bounding mixing times.
Preprint at http://www.math.gatech.edu/%7Etetali/RESEARCH/pubs.html.
[MW02] 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 (electronic), 10.1145/509907.510004. MR 2121194
[Nik05] N. Nikolov.
A product decomposition for the classical quasisimple groups.
http://www.arxiv.org/abs/math.GR/0510173, 2005.
[Nil91] A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210, 10.1016/0012-365X(91)90112-F. MR 1124768 (92j:05124)
[Nil04] A. Nilli, Tight estimates for eigenvalues of regular graphs, Electron. J. Combin. 11 (2004), no. 1, Note 9, 4 pp. (electronic). MR 2056091
[Nov02] T. Novikoff.
Asymptotic behavior of the random 3-regular bipartite graph.
Preprint, 2002.
[NZ96] Noam Nisan and David Zuckerman, Randomness is linear in space, J. Comput. System Sci. 52 (1996), no. 1, 43–52, 10.1006/jcss.1996.0004. MR 1375803 (97c:68050)
[Pap94] Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285 (95f:68082)
[Pin73] M. S. Pinsker.
On the complexity of a concentrator.
In 7th International Telegraffic Conference, pages 318/1-318/4, 1973.
[PU89] D. Peleg and E. Upfal, Constructing disjoint paths on expander graphs, Combinatorica 9 (1989), no. 3, 289–313, 10.1007/BF02125897. MR 1030383 (91h:05115)
[Rab80] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138, 10.1016/0022-314X(80)90084-0. MR 566880 (81f:10003)
[Rei05] 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, 10.1145/1060590.1060647. MR 2181639 (2006g:68118)
[Roi96] Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451–485, 10.1007/s002220050083. MR 1400314 (97e:20014)
[RS03] 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 (electronic), 10.1137/S009753970138462X. MR 1969401 (2004d:68052)
[RSU01] 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, 10.1109/18.910578. MR 1820480 (2002d:94068)
[RSW04] 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 (electronic), 10.1145/1007352.1007423. MR 2121630 (2005j:68120)
[RTV05] 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/.
[RU] T. Richardson and R. Urbanke.
Modern coding theory.
Draft of the book, http://lthcwww.epfl.ch/mct/index.php.
[RU01] 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, 10.1109/18.910577. MR 1820479 (2002c:94048)
[Rud91] Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Inc., New York, 1991. MR 1157815 (92k:46001)
[RV05] 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, 10.1007/11538462_37. MR 2193707
[RVW02] 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, 10.2307/3062153. MR 1888797 (2003c:05145)
[Sar04] Peter Sarnak, What is…an expander?, Notices Amer. Math. Soc. 51 (2004), no. 7, 762–763. MR 2072849
[Ser77] Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, New York, 1977. Translated from the second French edition by Leonard L. Scott; Graduate Texts in Mathematics, Vol. 42. MR 0450380 (56 #8675)
[Sha48] C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656. MR 0026286 (10,133e)
[Sha99] Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. (1999), no. 90, 145–168 (2001). MR 1813225 (2001m:22030)
[Sha04] G. Păun, G. Rozenberg, and A. Salomaa (eds.), 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. MR 2193911 (2006i:68002)
[Sie] 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.
[Sim03] 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). MR 2004402 (2004j:68194)
[Sip97] M. Sipser.
Introduction to the Theory of Computation.
PWS Publishing Company, 1997.
[Spi96] Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1723–1731, 10.1109/18.556668. Codes and complexity. MR 1465732 (98g:94034)
[SS77] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 0429721 (55 #2732)
[SS96] Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710–1722, 10.1109/18.556667. Codes and complexity. MR 1465731 (98d:94031)
[ST] H. Stark and A. Terras.
Zeta functions of finite graphs and coverings, part iii. Advances in Mathematics, to appear.
[Sud00] M. Sudan.
A crash course on coding theory.
http://theory.lcs.mit.edu/ ~madhu/coding/ibm/, 2000.
[Sud04] Madhu Sudan, Probabilistically checkable proofs, Computational complexity theory, IAS/Park City Math. Ser., vol. 10, Amer. Math. Soc., Providence, RI, 2004, pp. 349–389. MR 2089735
[Tan81] R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533–547, 10.1109/TIT.1981.1056404. MR 650686 (83i:94017)
[Tan84] R. Michael Tanner, Explicit concentrators from generalized 𝑁-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287–293, 10.1137/0605030. MR 752035 (85k:68080)
[Tho03] 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.
[TW96] Craig A. Tracy and Harold Widom, On orthogonal and symplectic matrix ensembles, Comm. Math. Phys. 177 (1996), no. 3, 727–754. MR 1385083 (97a:82055)
[UW87] Eli Upfal and Avi Wigderson, How to share memory in a distributed system, J. Assoc. Comput. Mach. 34 (1987), no. 1, 116–127, 10.1145/7531.7926. MR 882664 (88c:68009)
[Val76] 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). MR 0441008 (55 #13874)
[Val03] 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. MR 2027170 (2005d:19008)
[vL99] J. H. van Lint, Introduction to coding theory, 3rd ed., Graduate Texts in Mathematics, vol. 86, Springer-Verlag, Berlin, 1999. MR 1664228 (2000a:94001)
[vLW01] J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd ed., Cambridge University Press, Cambridge, 2001. MR 1871828 (2002i:05001)
[Vu05] 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, 10.1145/1060590.1060654. MR 2181644 (2006h:15025)
[Wig58] Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 0095527 (20 #2029)
[Wig06] 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.
[Wor99] 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. MR 1725006 (2000j:05114)
[WZ93] Avi Wigderson and David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Combinatorica 19 (1999), no. 1, 125–138, 10.1007/s004930050049. MR 1722214 (2000j:05081)
[Zuc05] D. Zuckerman.
Linear degree extractors and inapproximability of MAX-CLIQUE and chromatic number.
Manuscript, 2005.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|