Hard Metrics from Cayley Graphs of Abelian Groups
by Ilan Newman and Yuri Rabinovich
Theory of Computing, Volume 5(6), pp. 125-134, 2009
Bibliography with links to cited articles
[1] N. Alon and Y. Roichman: Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271–284, 1994. [doi:10.1002/rsa.3240050203].
[2] S. Arora, J. R. Lee, and A. Naor: Euclidean distortion and the sparsest cut. In Proc. 37th STOC, pp. 553–562. ACM Press, 2005. [STOC:1060590.1060673].
[3] Y. Aumann and Y. Rabani: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291–301, 1998. [doi:10.1137/S0097539794285983].
[4] J. Bourgain: On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.
[5] S. Chawla, A. Gupta, and H. Räcke: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):1–18, 2008. [doi:10.1145/1361192.1361199].
[6] M. M. Deza and M. Laurent: Geometry of Cuts and Metrics. Springer Verlag, 1997.
[7] A. Gupta, R. Krauthgamer, and J. R. Lee: Bounded geometries, fractals, and low-distortion embeddings. In Proc. 44th FOCS, pp. 534–543. IEEE Comp. Soc. Press, 2003.
[8] S. Hoory, N. Linial, and A. Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8].
[9] J. Justesen: A class of constructive asymptotically good algebraic codes. IEEE Trans. Inform. Theory, 18(5):652–656, 1972.
[10] S. Khot and A. Naor: Nonembeddability theorems via Fourier analysis. In Proc. 46th FOCS, pp. 101–112. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.61].
[11] N. Linial, E. London, and Y. Rabinovich: The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995. [doi:10.1007/BF01200757].
[12] F. J. MacWilliams and N. J. A. Sloane: The Theory of Error-Correcting Codes. North Holland, 1977.
[13] J. Matoušek: Lectures on Discrete Geometry. Springer, 2002.
[14] S. Rao: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proc. 15th Ann. Symp. on Comput. Geometry (SoCG’99), pp. 300–306. ACM Press, 1999. [doi:10.1145/304893.304983].
[15] 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].