Theory of Computing ------------------- Title : Hard Metrics from Cayley Graphs of Abelian Groups Authors : Ilan Newman and Yuri Rabinovich Volume : 5 Number : 6 Pages : 125-134 URL : https://theoryofcomputing.org/articles/v005a006 Abstract -------- Hard metrics are the class of extremal metrics with respect to embedding into Euclidean spaces: they incur Omega(log n) multiplicative distortion, which is as large as it can possibly get for any metric space of size n. Besides being very interesting objects akin to expanders and good error-correcting codes, and having a rich structure, such metrics are important for obtaining lower bounds in combinatorial optimization, e.g., on the value of MinCut/MaxFlow ratio for multicommodity flows. For more than a decade, a single family of hard metrics was known (Linial, London, Rabinovich (Combinatorica 1995) and Aumann, Rabani (SICOMP 1998)). Recently, a different family was found by Khot and Naor (FOCS 2005). In this paper we present a general method of constructing hard metrics. Our results extend to embeddings into negative type metric spaces and into l_1.