Expander graphs and their applications

Hoory, Shlomo; Linial, Nathan; Wigderson, Avi

doi:10.1090/S0273-0979-06-01126-8

Expander graphs and their applications
HTML articles powered by AMS MathViewer

by Shlomo Hoory, Nathan Linial and Avi Wigderson PDF

Bull. Amer. Math. Soc. 43 (2006), 439-561

References

IEEE Transactions on Information Theory

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. MR 2114305, DOI 10.1137/S0097539701389944
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. MR 975519, DOI 10.1016/0012-365X(88)90189-6

43nd IEEE Symposium on Foundations of Computer Science (Vancouver, BC)

N. Alon and M. Capalbo, Smaller explicit superconcentrators, Internet Math. 1 (2004), no. 2, 151–163. MR 2077222
Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman, Derandomized graph products, Comput. Complexity 5 (1995), no. 1, 60–75. MR 1319493, DOI 10.1007/BF01277956
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

Combinatorica

Proceedings of the 19th Annual ACM Symposium on Theory of Computing

Alon Amit and Nathan Linial, Random lifts of graphs: edge expansion, Combin. Probab. Comput. 15 (2006), no. 3, 317–332. MR 2216470, DOI 10.1017/S0963548305007273

Approximation Algorithms for NP-hard Problems

Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1–18. MR 1883559, DOI 10.1007/s004930200000
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. MR 1390029, DOI 10.1137/S0097539791221499
Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122. MR 1614328, DOI 10.1145/273865.273901
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. MR 1871947, DOI 10.1002/rsa.10003
N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
Noga Alon, On the edge-expansion of graphs, Combin. Probab. Comput. 6 (1997), no. 2, 145–152. MR 1447810, DOI 10.1017/S096354839700299X
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
N. Alon and V. D. Milman, $\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73–88. MR 782626, DOI 10.1016/0095-8956(85)90092-9
Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284. MR 1262979, DOI 10.1002/rsa.3240050203
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
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. MR 2121604, DOI 10.1145/1007352.1007355
Sanjeev Arora and Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, J. ACM 45 (1998), no. 1, 70–122. MR 1614328, DOI 10.1145/273865.273901
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, DOI 10.1002/0471722154

44nd IEEE Symposium on Foundations of Computer Science (Cambridge, MA)

http://www.math.cmu.edu/~af1p/papers.html

William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 385456, DOI 10.2307/1970980
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. MR 1662203, DOI 10.1002/(SICI)1098-2418(1999010)14:1<87::AID-RSA5>3.0.CO;2-O
Yonatan Bilu and Shlomo Hoory, On codes from hypergraphs, European J. Combin. 25 (2004), no. 3, 339–354. MR 2036471, DOI 10.1016/j.ejc.2003.10.002
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. MR 651465, DOI 10.1016/0020-0190(81)90050-8
H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh, Are bitvectors optimal?, SIAM J. Comput. 31 (2002), no. 6, 1723–1744. MR 1954872, DOI 10.1137/S0097539702405292

44nd IEEE Symposium on Foundations of Computer Science (Cambridge, MA, 2003)

Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986. Set systems, hypergraphs, families of vectors and combinatorial probability. MR 866142
Aline Bonami, Étude des coefficients de Fourier des fonctions de $L^{p}(G)$, Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 2, 335–402 (1971) (French, with English summary). MR 283496
J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), no. 1-2, 46–52. MR 815600, DOI 10.1007/BF02776078
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

The 28th Annual Symposium on Foundations of Computer Science

Piotr Berman and Georg Schnitger, On the complexity of approximating the independent set problem, Inform. and Comput. 96 (1992), no. 1, 77–94. MR 1142227, DOI 10.1016/0890-5401(92)90056-L
Eli Ben-Sasson and Avi Wigderson, Short proofs are narrow—resolution made simple, J. ACM 48 (2001), no. 2, 149–169. MR 1868713, DOI 10.1145/375827.375835
Peter Buser, A note on the isoperimetric constant, Ann. Sci. École Norm. Sup. (4) 15 (1982), no. 2, 213–230. MR 683635
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, DOI 10.1007/978-3-662-07441-1
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
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
Sebastian M. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory Ser. B 96 (2006), no. 3, 367–373. MR 2220665, DOI 10.1016/j.jctb.2005.09.002

IEEE Conference on Computational Complexity

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. MR 1848805
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. MR 2121193, DOI 10.1145/509907.510003
James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1

Proceedings of the 15th Annual ACM Symposium on Theory of Computing

Reinhard Diestel, Graphentheorie, Springer-Lehrbuch. [Springer Textbook], Springer-Verlag, Berlin, 1996 (German). MR 1411445, DOI 10.1007/978-3-662-07551-7
Michel Marie Deza and Monique Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. MR 1460488, DOI 10.1007/978-3-642-04295-9
Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002-9947-1984-0743744-X
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, DOI 10.1017/CBO9780511615825
P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 120167
William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020

32nd IEEE Symposium on Foundations of Computer Science

Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241. MR 637828, DOI 10.1007/BF02579329

Proceedings of the 21st Annual ACM Symposium on Theory of Computing

Joel Friedman, The spectra of infinite hypertrees, SIAM J. Comput. 20 (1991), no. 5, 951–961. MR 1115660, DOI 10.1137/0220058
Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487–525. MR 1208809, DOI 10.1215/S0012-7094-93-06921-9
Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19–35. MR 1978881, DOI 10.1215/S0012-7094-03-11812-8
Joel Friedman and Avi Wigderson, On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), no. 1, 43–65. MR 1325271, DOI 10.1007/BF01294459
R. G. Gallager, Low-density parity-check codes, IRE Trans. IT-8 (1962), 21–28. MR 0136009, DOI 10.1109/tit.1962.1057683
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. MR 633542, DOI 10.1016/0022-0000(81)90040-4
David Gillman, A Chernoff bound for random walks on expander graphs, SIAM J. Comput. 27 (1998), no. 4, 1203–1220. MR 1621958, DOI 10.1137/S0097539794268765
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, DOI 10.1007/978-3-642-78240-4

http://www.eccc.uni-trier.de/eccc/

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. MR 2115065, DOI 10.1090/S0273-0979-04-01037-7

On the Spectrum of Graphs and Their Universal Covering

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 450121, DOI 10.1016/0095-8956(77)90068-5
Mikhael Gromov, Filling Riemannian manifolds, J. Differential Geom. 18 (1983), no. 1, 1–147. MR 697984
M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146. MR 1978492, DOI 10.1007/s000390300002
Johan Håstad, Clique is hard to approximate within $n^{1-\epsilon }$, Acta Math. 182 (1999), no. 1, 105–142. MR 1687331, DOI 10.1007/BF02392825
R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J. 29 (1950), 147–160. MR 35935, DOI 10.1002/j.1538-7305.1950.tb00463.x

On graphs of high girth

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. MR 2102266, DOI 10.1016/j.jctb.2004.06.001

Handbook of discrete and computational geometry

Proceedings of the 26th Annual ACM Symposium on Theory of Computing

Mark Jerrum, Counting, sampling and integrating: algorithms and complexity, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2003. MR 1960003, DOI 10.1007/978-3-0348-8005-3
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, DOI 10.1090/conm/026/737400
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
S. Jimbo and A. Maruoka, Expanders obtained from affine transformations, Combinatorica 7 (1987), no. 4, 343–355. MR 931192, DOI 10.1007/BF02579322
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, DOI 10.1016/0890-5401(89)90067-9

Approximation Algorithms for NP-Hard Problems

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. MR 2147852, DOI 10.1145/1008731.1008738
Nabil Kahale, Eigenvalues and expansion of regular graphs, J. Assoc. Comput. Mach. 42 (1995), no. 5, 1091–1106. MR 1412045, DOI 10.1145/210118.210136
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
Martin Kassabov, Kazhdan constants for $\textrm {SL}_n({\Bbb Z})$, Internat. J. Algebra Comput. 15 (2005), no. 5-6, 971–995. MR 2197816, DOI 10.1142/S0218196705002712

http://www.arxiv.org/abs/ math.GR/0505624

Func. Anal. Appl.

29th IEEE Symposium on Foundations of Computer Science (White Planes)

http://www.arxiv.org/abs/math.GR/0510562

T. W. Körner, Fourier analysis, 2nd ed., Cambridge University Press, Cambridge, 1989. MR 1035216

AMS Conference on Probabilistic Computational Complexity

The 46th Annual Symposium on Foundations of Computer Science

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. MR 1957562
Nathan Linial and Eran London, On the expansion rate of Margulis expanders, J. Combin. Theory Ser. B 96 (2006), no. 3, 436–442. MR 2220670, DOI 10.1016/j.jctb.2005.09.001
Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355, DOI 10.1007/BF01200757
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. MR 1769197, DOI 10.1006/jctb.2000.1953
N. Linial, A. Magen, and A. Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002), no. 2, 380–394. MR 1911665, DOI 10.1007/s00039-002-8251-y
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. MR 1820478, DOI 10.1109/18.910576
Alexander Lubotzky and Tatiana Nagnibeda, Not every uniform tree covers Ramanujan graphs, J. Combin. Theory Ser. B 74 (1998), no. 2, 202–212. MR 1654133, DOI 10.1006/jctb.1998.1843
J. R. Lee and A. Naor, Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$, Geom. Funct. Anal. 14 (2004), no. 4, 745–747. MR 2084978, DOI 10.1007/s00039-004-0473-8
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. MR 1892859, DOI 10.1006/jcss.2001.1786
László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492
A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
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. MR 1753034, DOI 10.1145/331524.331526
Nathan Linial and Eyal Rozenman, Random lifts of graphs: perfect matchings, Combinatorica 25 (2005), no. 4, 407–424. MR 2143247, DOI 10.1007/s00493-005-0024-8
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type $\~A_d$, European J. Combin. 26 (2005), no. 6, 965–993. MR 2143204, DOI 10.1016/j.ejc.2004.06.007
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, DOI 10.1007/978-3-0346-0332-4
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, DOI 10.1090/dimacs/010/08
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, DOI 10.1017/s0963548397003349
G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767
G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), no. 1, 71–78. MR 671147, DOI 10.1007/BF02579283
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
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203–216. MR 629617, DOI 10.1016/0024-3795(81)90150-6
Moshe Morgenstern, Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$, J. Combin. Theory Ser. B 62 (1994), no. 1, 44–62. MR 1290630, DOI 10.1006/jctb.1994.1054
Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995. MR 1344451, DOI 10.1017/CBO9780511814075
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. MR 1931846, DOI 10.1109/SFCS.2000.892137
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. Inform. Theory IT-23 (1977), no. 2, 157–166. MR 439403, DOI 10.1109/tit.1977.1055688
F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Mathematical Library, Vol. 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0465509
F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Mathematical Library, Vol. 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0465509
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

http://www.math.gatech.edu/%7Etetali/RESEARCH/pubs.html

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. MR 2121194, DOI 10.1145/509907.510004

http://www.arxiv.org/abs/math.GR/0510173

A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210. MR 1124768, DOI 10.1016/0012-365X(91)90112-F
A. Nilli, Tight estimates for eigenvalues of regular graphs, Electron. J. Combin. 11 (2004), no. 1, Note 9, 4. MR 2056091
Noam Nisan and David Zuckerman, Randomness is linear in space, J. Comput. System Sci. 52 (1996), no. 1, 43–52. MR 1375803, DOI 10.1006/jcss.1996.0004
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285

7th International Telegraffic Conference

D. Peleg and E. Upfal, Constructing disjoint paths on expander graphs, Combinatorica 9 (1989), no. 3, 289–313. MR 1030383, DOI 10.1007/BF02125897
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
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. MR 2181639, DOI 10.1145/1060590.1060647
Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451–485. MR 1400314, DOI 10.1007/s002220050083
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. MR 1969401, DOI 10.1137/S009753970138462X
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. MR 1820480, DOI 10.1109/18.910578
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. MR 2121630, DOI 10.1145/1007352.1007423

http://www.eccc.uni-trier.de/eccc/

http://lthcwww.epfl.ch/mct/index.php

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. MR 1820479, DOI 10.1109/18.910577
Walter Rudin, Functional analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1991. MR 1157815
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. MR 2193707, DOI 10.1007/11538462_{3}7
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. MR 1888797, DOI 10.2307/3062153
Peter Sarnak, What is$\dots$an expander?, Notices Amer. Math. Soc. 51 (2004), no. 7, 762–763. MR 2072849
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380
C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656. MR 26286, DOI 10.1002/j.1538-7305.1948.tb01338.x
Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145–168 (2001). MR 1813225
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

http://www.cs.nyu.edu/faculty/siegel/SCIAM.pdf

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, DOI 10.1007/s10107-003-0447-x

Introduction to the Theory of Computation

Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1723–1731. Codes and complexity. MR 1465732, DOI 10.1109/18.556668
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006
Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, 1710–1722. Codes and complexity. MR 1465731, DOI 10.1109/18.556667

Advances in Mathematics

http://theory.lcs.mit.edu/~madhu/coding/ibm/

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, DOI 10.1090/pcms/010/12
R. Michael Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27 (1981), no. 5, 533–547. MR 650686, DOI 10.1109/TIT.1981.1056404
R. Michael Tanner, Explicit concentrators from generalized $N$-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287–293. MR 752035, DOI 10.1137/0605030

The Interplanetary Network Progress Report 42-154

Craig A. Tracy and Harold Widom, On orthogonal and symplectic matrix ensembles, Comm. Math. Phys. 177 (1996), no. 3, 727–754. MR 1385083
Eli Upfal and Avi Wigderson, How to share memory in a distributed system, J. Assoc. Comput. Mach. 34 (1987), no. 1, 116–127. MR 882664, DOI 10.1145/7531.7926
Leslie G. Valiant, Graph-theoretic properties in computational complexity, J. Comput. System Sci. 13 (1976), no. 3, 278–285. MR 441008, DOI 10.1016/S0022-0000(76)80041-4
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
J. H. van Lint, Introduction to coding theory, 3rd ed., Graduate Texts in Mathematics, vol. 86, Springer-Verlag, Berlin, 1999. MR 1664228, DOI 10.1007/978-3-642-58575-3
J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd ed., Cambridge University Press, Cambridge, 2001. MR 1871828, DOI 10.1017/CBO9780511987045
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. MR 2181644, DOI 10.1145/1060590.1060654
Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 95527, DOI 10.2307/1970008

Proc. of the 2006 International Congress of Mathematicians

http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/W06.pdf

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
Avi Wigderson and David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Combinatorica 19 (1999), no. 1, 125–138. MR 1722214, DOI 10.1007/s004930050049