Monotone Expanders: Constructions and Applications

by Zeev Dvir and Avi Wigderson

Theory of Computing, Volume 6(12), pp. 291-308, 2010

Bibliography with links to cited articles

[1]   Miklós Ajtai, Henryk Iwaniec, János Komlós, János Pintz, and Endre Szemerédi: Construction of a thin set with small Fourier coefficients. Bull. Lond. Math. Soc., 22:583–590, 1990. [doi:10.1112/blms/22.6.583]

[2]   Noga Alon, Oded Schwartz, and Assaf Shapira: An elementary construction of constant-degree expanders. Combin. Probab. Comput., 17(3):319–327, 2008. [doi:10.1017/S0963548307008851]

[3]   Noga Alon, Paul Seymour, and Robin Thomas: A separator theorem for graphs with an excluded minor and its applications. In Proc. 22nd STOC, pp. 293–299, New York, NY, USA, 1990. ACM Press. [doi:10.1145/100216.100254]

[4]   Boaz Barak, Russell Impagliazzo, Amir Shpilka, and Avi Wigderson: Definition and existence of dimension expanders, 2004. Discussion (no written record).

[5]   Frank Bernhart and Paul C. Kainen: The book thickness of a graph. J. Combin. Theory Ser. B, 27(3):320–331, 1979. [doi:10.1016/0095-8956(79)90021-2]

[6]   Jean Bourgain: Expanders and dimensional expansion. C. R. Math., 347(7–8):357–362, 2009. [doi:10.1016/j.crma.2009.02.009]

[7]   Jean Bourgain and Alex Gamburd: On the spectral gap for finitely-generated subgroups of SU(2). Invent. Math., 171:83–121, sep 2007. [doi:10.1007/s00222-007-0072-z]

[8]   Emmanuel Breuillard: A strong Tits alternative. Technical Report arXiv:0804.1395, ArXiv e-print repository, April 2008. [arXiv:0804.1395v1]

[9]   Jonathan F. Buss and Peter W. Shor: On the pagenumber of planar graphs. In Proc. 16th STOC, pp. 98–100, New York, NY, USA, 1984. ACM Press. [doi:10.1145/800057.808670]

[10]   Fan R. K. Chung, Frank Thomson Leighton, and Arnold L. Rosenberg: Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Algebr. Discrete Methods, 8(1):33–58, 1987. [doi:10.1137/0608002]

[11]   Zeev Dvir and Amir Shpilka: Towards dimension expanders over finite fields. In Proc. IEEE 23rd Ann. Conf. Comput. Complex. (CCC), pp. 304–310, Washington, DC, USA, 2008. IEEE Comp. Soc. Press. [doi:10.1109/CCC.2008.19]

[12]   Zvi Galil, Ravi Kannan, and Endre Szemerédi: On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines. In Proc. 18th STOC, pp. 39–49, New York, NY, USA, 1986. ACM Press. [doi:10.1145/12130.12135]

[13]   Aram Harrow: Quantum expanders from any classical Cayley graph expander. Quantum Inf. Comput., 8(8/9):715–721, 2008. QIC Volume 8.

[14]   Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43:439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]

[15]   Martin Kassabov, Alexander Lubotzky, and Nikolay Nikolov: Finite simple groups as expanders. Proc. Natl. Acad. Sci. USA, 103(16):6116–6119, 2006. [doi:10.1073/pnas.0510337103]

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

[17]   Richard J. Lipton and Robert E. Tarjan: A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016]

[18]   Richard J. Lipton and Robert E. Tarjan: Applications of a planar separator theorem. SIAM J. Comput., 9(3):615–627, 1980. [doi:10.1137/0209046]

[19]   Alexander Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [doi:10.1007/BF02126799]

[20]   Alexander Lubotzky and Benjamin Weiss: Groups and expanders. In Expanding graphs (Princeton, NJ, 1992), DIMACS Ser. 10, pp. 95–109, Providence, RI, 1993. AMS.

[21]   Alexander Lubotzky and Efim Zelmanov: Dimension expanders. J. Algebra, 319(2):730–738, 2008. [doi:10.1016/j.jalgebra.2005.12.033]

[22]   G. 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.

[23]   Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, and William T. Trotter: On determinism versus non-determinism and related problems. In Proc. 24th Ann. Symp. Found. Comput. Sci. (SFCS), pp. 429–438, Washington, DC, USA, 1983. IEEE Comp. Soc. Press. [doi:10.1109/SFCS.1983.39]

[24]   Nicholas Pippenger: Advances in pebbling (preliminary version). In Proc. 9th Colloq. Autom. Lang. Program. (ICALP), pp. 407–417, London, UK, 1982. Springer-Verlag. [doi:10.1007/BFb0012787]

[25]    Alexander Razborov, Endre Szemerédi, and Avi Wigderson: Constructing small sets that are uniform in arithmetic progressions. Combin. Probab. Comput., 2:513–518, 1993. [doi:10.1017/S0963548300000870]

[26]   Omer Reingold, Salil Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math., 155(1):157–187, 2002. [JSTOR:3062153]

[27]   Rahul Santhanam: On separators, segregators and time versus space. In Proc. IEEE 16th Ann. Conf. Comput. Complex. (CCC), pp. 286–294, Washington, DC, USA, 2001. IEEE Comp. Soc. Press. [doi:10.1109/CCC.2001.933895]

[28]   Avi Wigderson: Expanders: Old and new applications and problems. (A lecture at IPAM, UCLA), February 2004.

[29]   Avi Wigderson and David Xiao: Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Theory of Computing, 4(1):53–76, 2008. [doi:10.4086/toc.2008.v004a003]