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].