[1]   Miklós Ajtai, János Komlós, and Endre Szemerédi: Sorting in clog n parallel steps. Combinatorica, 3(1):1–19, 1983.

[2]   Noga Alon: Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986.

[3]   Noga Alon, Zvi Galil, and Vitali D. Milman: Better expanders and superconcentrators. Journal of Algorithms, 8(3):337–347, 1987. [JAlg:10.1016/0196-6774(87)90014-9].

[4]   Noga Alon, Alexander Lubotzky, and Avi Wigderson: Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract). In Proc. of the 42nd Annual Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 630–637. IEEE Computer Soc., Los Alamitos, CA, 2001. [FOCS:10.1109/SFCS.2001.959939].

[5]   Noga Alon and Vitali D. Milman: λ₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73–88, 1985. [JCombThB:10.1016/0095-8956(85)90092-9].

[6]   Alon Amit and Nathan Linial: Random graph coverings. I. General theory and graph connectivity. Combinatorica, 22(1):1–18, 2002. [Combinatorica:er6qljcyq3v8pyd2].

[7]   Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp. 612–621. ACM Press, 2003. [STOC:780542.780631].

[8]   Yonatan Bilu and Nati Linial: Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap. In Proc. of the 45th Annual Symposium on Foundations of Computer Science, pp. 404–412, Rome, Italy, 17-19 October 2004. IEEE. [FOCS:10.1109/FOCS.2004.19].

[9]   Andrei Broder and Eli Shamir: On the second eigenvalue of random regular graphs (preliminary version). In Proc. of the 28th Annual Symposium on Foundations of Computer Science, pp. 286–294, Los Angeles, California, 12–14 October 1987. IEEE.

[10]   Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson: Randomness conductors and constant-degree lossless expanders. In Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp. 659–668. ACM Press, 2002. [STOC:509907.510003].

[11]   Persi Diaconis and Mehrdad Shahshahani: On the eigenvalues of random matrices. J. Appl. Probab., 31A:49–62, 1994.

[12]   Martin Eichler: Quaternäre quadratische Formen und die Riemannsche Vermutung für die Kongruenzzetafunktion. Arch. Math., 5:355–366, 1954.

[13]   Joel Friedman: A proof of Alon’s second eigenvalue conjecture. Memoirs of the AMS, to appear. [arXiv:cs.DM/0405020].

[14]   Ofer Gabber and Zvi Galil: Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407–420, June 1981. [JCSS:10.1016/0022-0000(81)90040-4].

[15]   Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman: Security preserving amplification of hardness. In Proc. of the 31st Annual Symposium on Foundations of Computer Science, volume I, pp. 318–326, St. Louis, Missouri, 22–24 October 1990. IEEE.

[16]   Misha Gromov: Spaces and questions. Geometric and Functional Analysis, pp. 118–161, 2000. Part I of Special Volume on GAFA 2000 (Tel Aviv, 1999).

[17]   Jonathan L. Gross: Every connected regular graph of even degree is a Schreier coset graph. Journal of Combinatorial Theory. Series B, 22(3):227–232, 1977. [JCombThB:10.1016/0095-8956(77)90068-5].

[18]    Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for network algorithms. In Proc. of the 26th Annual ACM Symposium on the Theory of Computing, pp. 356–364, Montréal, Québec, Canada, 23–25 May 1994. [STOC:195058.195190].

[19]   Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. of the 29th Annual ACM Symposium on Theory of Computing, pp. 220–229, El Paso, Texas, 4–6 May 1997. [STOC:258533.258590].

[20]   Shuji Jimbo and Akira Maruoka: Expanders obtained from affine transformations. Combinatorica, 7(4):343–355, 1987.

[21]   Nigel J. Kalton and James W. Roberts: Uniformly exhaustive submeasures and nearly additive set functions. Transactions of the American Mathematical Society, 278(2):803–816, 1983.

[22]   Martin Kassabov: Symmetric groups and expander graphs. arxiv:math.GR/0505624. [arXiv:math.GR/0505624].

[23]   Martin Kassabov: Universal lattices and unbounded rank expanders. arxiv:math.GR/0502237. [arXiv:math.GR/0502237].

[24]   Martin Kassabov and Nikolay Nikolov: Universal lattices and property τ. arxiv:math.GR/0502112. [arXiv:math.GR/0502112].

[25]   David Kazhdan: On the connection of the dual space of a group with the structure of its closed subgroups (Russian). Funkcional. Anal. i Prilozh., 1:71–74, 1967.

[26]   Maria Klawe: Limitations on explicit constructions of expanding graphs. SIAM J. Comput., 13(1):156–166, 1984. [SICOMP:13/0213011].

[27]   László Lovász and Peter Winkler: Mixing times. In Microsurveys in discrete probability (Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 85–133. Amer. Math. Soc., Providence, RI, 1998.

[28]   A. Lubotzky and B. Weiss: Groups and expanders. In Expanding graphs (Princeton, NJ, 1992), volume 10 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 95–109. Amer. Math. Soc., Providence, RI, 1993.

[29]   Alex Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [Combinatorica:k285687344657q53].

[30]   Alexander Lubotzky: Discrete groups, expanding graphs and invariant measures. Birkhäuser Verlag, Basel, 1994.

[31]   Alexander Lubotzky and Igor Pak: The product replacement algorithm and Kazhdan’s property (T). Journal of the American Mathematical Society, 14(2):347–363 (electronic), 2001. [JAMS:2001-14-02/S0894-0347-00-00356-8].

[32]   Gregory A. Margulis: Explicit constructions of expanders. Problemy Peredači Informacii, 9(4):71–80, 1973.

[33]   Gregory A. Margulis: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

[34]   Roy Meshulam and Avi Wigderson: Expanders from symmetric codes. In Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp. 669–677. ACM Press, 2002. [STOC:509907.510004].

[35]   Moshe Morgenstern: Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory. Series B, 62(1):44–62, 1994. [JCombThB:10.1006/jctb.1994.1054].

[36]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM Journal on Computing, 22(4):838–856, August 1993. [SICOMP:22/0222053].

[37]   Nikolay Nikolov: On the commutator width of perfect groups. Bull. London Math. Soc., 36(1):30–36, 2004. [BLMS:10.1112/S0024609303002601].

[38]   Oystein Ore: Some remarks on commutators. Proc. Amer. Math. Soc., 2:307–314, 1951.

[39]   Mark S. Pinsker: On the complexity of a concentrator. In Proc. of the 7th Annual Teletraffic Conference, pp. 318/1–318/4, Stockholm, 1973.

[40]   Nicholas Pippenger: Sorting and selecting in rounds. SIAM Journal on Computing, 16(6):1032–1038, December 1987. [SICOMP:16/0216066].

[41]   Nicholas Pippenger and Andrew C. Yao: Rearrangeable networks with limited depth. SIAM Journal on Algebraic and Discrete Methods, 3(4):411–417, 1982. [SIMAX:03/0603041].

[42]   Omer Reingold, Salil Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math. (2), 155(1):157–187, 2002. [arXiv:math.CO/0406038].

[43]   Atle Selberg: On the estimation of Fourier coefficients of modular forms. In Proc. of the Sympos. Pure Math., volume VIII, pp. 1–15. Amer. Math. Soc., Providence, R.I., 1965.

[44]   Michael Sipser: Expanders, randomness, or time versus space. Journal of Computer and System Sciences, 36(3):379–383, June 1988. [JCSS:10.1016/0022-0000(88)90035-9].

[45]   Michael Sipser and Daniel A. Spielman: Expander codes. IEEE Transactions on Information Theory, 42(6, part 1):1710–1722, 1996. [TIT:10.1109/18.556667].

[46]   Daniel A. Spielman: Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6, part 1):1723–1731, 1996. [TIT:10.1109/18.556668].

[47]   Michael R. Tanner: Explicit concentrators from generalized n-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287–293, 1984. [SIMAX:05/0605030].

[48]   Alasdair Urquhart: Hard examples for resolution. Journal of the Association for Computing Machinery, 34(1):209–219, 1987. [JACM:7531.8928].

[49]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. of the 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Comput. Sci., pp. 162–176. Springer, Berlin, 1977.

[50]   Avi Wigderson and David Zuckerman: Expanders that beat the eigenvalue bound: explicit construction and applications. Combinatorica, 19(1):125–138, 1999. [Combinatorica:wcjlnyjmdxf30b9x].