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]