Iterative Construction of Cayley Expander Graphs
by Eyal Rozenman, Aner Shalev, and Avi Wigderson
Theory of Computing, Volume 2(5), pp. 91-120, 2006
Bibliography with links to cited articles
| [1] |
Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of
Computing, Montréal, Québec, Canada, 23-25 May 1994. |
| [2] |
Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of
Computing, El Paso, Texas, 4-6 May 1997. |
| [3] |
Miklós Ajtai, János Komlós, and Endre Szemerédi: Sorting
in c logn parallel steps.
Combinatorica, 3(1):1-19, 1983. |
| [4] |
Noga Alon: Eigenvalues and expanders.
Combinatorica, 6(2):83-96, 1986. |
| [5] |
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]. |
| [6] |
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]. |
| [7] |
Noga Alon and Vitali D. Milman: λ 1, 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]. |
| [8] |
Alon Amit and Nathan Linial: Random graph coverings. I. General
theory and graph connectivity.
Combinatorica, 22(1):1-18, 2002.
[Combinatorica:er6qljcyq3v8pyd2]. |
| [9] |
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]. |
| [10] |
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 [22], pp. 404-412.
[FOCS:10.1109/FOCS.2004.19]. |
| [11] |
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 [20], pp. 286-294. |
| [12] |
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]. |
| [13] |
Persi Diaconis and Mehrdad Shahshahani: On the eigenvalues of random
matrices.
J. Appl. Probab., 31A:49-62, 1994. |
| [14] |
Martin Eichler: Quaternäre quadratische Formen und die Riemannsche
Vermutung für die Kongruenzzetafunktion.
Arch. Math., 5:355-366, 1954. |
| [15] |
Joel Friedman: A proof of Alon's second eigenvalue conjecture.
Memoirs of the AMS, to appear.
[arXiv:cs.DM/0405020]. |
| [16] |
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]. |
| [17] |
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 [21], pp. 318-326. |
| [18] |
Misha Gromov: Spaces and questions.
Geometric and Functional Analysis, pp. 118-161, 2000.
Part I of Special Volume on GAFA 2000 (Tel Aviv, 1999). |
| [19] |
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]. |
| [20] |
IEEE.
28th Annual Symposium on Foundations of Computer Science, Los
Angeles, California, 12-14 October 1987. |
| [21] |
IEEE.
31st Annual Symposium on Foundations of Computer Science,
volume I, St. Louis, Missouri, 22-24 October 1990. |
| [22] |
IEEE.
45th Annual Symposium on Foundations of Computer Science, Rome,
Italy, 17-19 October 2004. |
| [23] |
Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for
network algorithms.
In ACM [1], pp. 356-364.
[STOC:195058.195190]. |
| [24] |
Russell Impagliazzo and Avi Wigderson: P = BPP if
E requires exponential circuits: Derandomizing the XOR lemma.
In ACM [2], pp. 220-229.
[STOC:258533.258590]. |
| [25] |
Shuji Jimbo and Akira Maruoka: Expanders obtained from affine
transformations.
Combinatorica, 7(4):343-355, 1987. |
| [26] |
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. |
| [27] |
Martin Kassabov: Symmetric groups and expander graphs.
arxiv:math.GR/0505624.
[arXiv:math.GR/0505624]. |
| [28] |
Martin Kassabov: Universal lattices and unbounded rank expanders.
arxiv:math.GR/0502237.
[arXiv:math.GR/0502237]. |
| [29] |
Martin Kassabov and Nikolay Nikolov: Universal lattices and property
τ.
arxiv:math.GR/0502112.
[arXiv:math.GR/0502112]. |
| [30] |
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. |
| [31] |
Maria Klawe: Limitations on explicit constructions of expanding graphs.
SIAM J. Comput., 13(1):156-166, 1984.
[SICOMP:13/0213011]. |
| [32] |
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. |
| [33] |
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. |
| [34] |
Alex Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs.
Combinatorica, 8(3):261-277, 1988.
[Combinatorica:k285687344657q53]. |
| [35] |
Alexander Lubotzky: Discrete groups, expanding graphs and invariant
measures.
Birkhäuser Verlag, Basel, 1994. |
| [36] |
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:jams/2001-14-02/S0894-0347-00-00356-8]. |
| [37] |
Gregory A. Margulis: Explicit constructions of expanders.
Problemy Peredaci Informacii, 9(4):71-80, 1973. |
| [38] |
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. |
| [39] |
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]. |
| [40] |
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]. |
| [41] |
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]. |
| [42] |
Nikolay Nikolov: On the commutator width of perfect groups.
Bull. London Math. Soc., 36(1):30-36, 2004.
[BLMS:10.1112/S0024609303002601]. |
| [43] |
Oystein Ore: Some remarks on commutators.
Proc. Amer. Math. Soc., 2:307-314, 1951. |
| [44] |
Mark S. Pinsker: On the complexity of a concentrator.
In Proc. of the 7th Annual Teletraffic Conference, pp.
318/1-318/4, Stockholm, 1973. |
| [45] |
Nicholas Pippenger: Sorting and selecting in rounds.
SIAM Journal on Computing, 16(6):1032-1038, December 1987.
[SICOMP:16/0216066]. |
| [46] |
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]. |
| [47] |
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]. |
| [48] |
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. |
| [49] |
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]. |
| [50] |
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]. |
| [51] |
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]. |
| [52] |
Michael R. Tanner: Explicit concentrators from generalized n-gons.
SIAM Journal on Algebraic Discrete Methods, 5(3):287-293,
1984.
[SIMAX:05/0605030]. |
| [53] |
Alasdair Urquhart: Hard examples for resolution.
Journal of the Association for Computing Machinery,
34(1):209-219, 1987.
[JACM:7531.8928]. |
| [54] |
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. |
| [55] |
Avi Wigderson and David Zuckerman: Expanders that beat the eigenvalue
bound: explicit construction and applications.
Combinatorica, 19(1):125-138, 1999.
[Combinatorica:wcjlnyjmdxf30b9x]. |
This file has been generated by bibtex2html 1.81.