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.