Authors Ilan Newman, Yuri Rabinovich,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134
www.theoryofcomputing.org
Hard Metrics From Cayley Graphs Of
Abelian Groups
Ilan Newman Yuri Rabinovich∗
Received: April 29, 2008; published: July 3, 2009.
Abstract: Hard metrics are the class of extremal metrics with respect to embedding into
Euclidean spaces; they incur Ω(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 `1 .
ACM Classification: F.2.2, G.2.2
AMS Classification: 11J83, 52C45, 05C25
Key words and phrases: Metric Embedding, Hard Metrics
1 Introduction
A famous theorem of Bourgain [4] states that every finite metric space V = (X, d) of size n = |X| can
be embedded into a Euclidean space with multiplicative distortion at most O(log n). We call a metric
space V hard with respect to `2 if any embedding of V into a Euclidean space (of any dimension) has
a multiplicative distortion Ω(log n). Similarly, we call a metric space V hard with respect to M, where
M is a class of metric spaces (e. g., M = ` p or NEG), if any embedding of V into M has multiplicative
∗ Supported in part by a grant ISF-247-020-10.5
2009 Ilan Newman and Yuri Rabinovich
Licensed under a Creative Commons Attribution License DOI: 10.486/toc.2009.v005a006
I. N EWMAN , AND Y. R ABINOVICH
distortion Ω(log n). When we use the term hard without specifying M, we always mean with respect to
M = `2 .
When studying a special class of metric spaces, perhaps the most natural first question is whether
this class contains hard metrics with respect to `2 . Many fundamental results in the modern theory of
finite metric spaces may be viewed as a negative answer to this question for some special important class
of metrics. E. g., Arora et al. [2] (improving on Chawla et al. [5]) show this for Negative Type metrics,
Rao [14] for planar metrics, and Gupta et al. [7] for doubling metrics. For a long time (since Linial,
London and Rabinovich [11] and Rabani and Aumann [3]), the only known family of hard metrics was,
essentially, the shortest-path metric of constant-degree expander graphs. It was even suggested that in
some vague sense these are essentially the only hard metrics. Recently, however, Khot and Naor [10]
constructed a different family of hard metrics by considering certain quotient spaces of Zn2 equipped
with the Hamming distance.
The starting point of the current research was a plausible conjecture that a circular metric cannot be
hard, where by circular we mean a metric on the underlying space Zn , such that d(a, b) depends solely
on ((a − b) mod n). Rather surprisingly, the conjecture turns out to be false, and, moreover, it fails
not only for Zn , but for any Abelian group H. More precisely, it is always possible to choose a set A
of generators for H, so that the shortest-path metric of the corresponding Cayley graph G(H, A) is hard
with respect to `2 , `1 and NEG. In the special case of Zn2 , good sets of generators are closely related to
error-correcting codes of constant rate and linear distance.
Our construction is both simple to describe and easy to analyze. It differs from that of [11, 3], as the
degree of such Cayley graphs is necessarily not bounded. Moreover, the construction of [10], despite
very different description and analysis, can be shown to produce the same metric space as does our
construction in the special case of Zn2 .
Note: Although in what follows we restrict the discussion to Euclidean spaces, the same method can
be used to show the hardness of the metrics that we construct also with respect to the much richer class
NEG of “negative type metrics” and consequently to `1 .
2 Definitions
Let (X, d) be a metric space which one wants to embed into another metric space A = (H, ν). The
multiplicative distortion, or simply the distortion of embedding (X, d) into A is defined as
ν(φ (x), φ (y)) d(x, y)
cA (d) = dist(d ,→ A) = min max · max .
φ :X→H x,y∈X d(x, y) x,y∈X ν(φ (x), φ (y))
We use the terms Euclidean metrics and `2 -metrics interchangeably.
We say that a metric space V = (X, d) is of negative type if there is a map f from X to an Euclidean
space such that for all x, y ∈ X we have d(x, y) = k f (x) − f (y)k22 . (So all triangles spanned by the image
of X are acute.) NEG denotes the class of negative type metrics.
It is well known that `1 metrics are of negative type (cf. [6], Part 1, Chapter 6.1 for a comprehensive
discussion and historical notes).
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 126
H ARD M ETRICS F ROM C AYLEY G RAPHS O F A BELIAN G ROUPS
3 Abelian Groups
Let G = (V, E) be a d-regular connected graph on n vertices, and let µG be its shortest-path metric. For
∆ : V (G) ×V (G) → R+ , consider the following projective quadratic form, often called a Poincaré form:
∑(i, j)∈E(G) ∆2 (i, j)
F(∆) = (3.1)
∑i< j∈V (G) ∆2 (i, j)
To obtain distortion lower bounds on µG , we use the standard (dual) method of comparing Poincaré
forms (see, e. g., [11, 13]). Our first step is to get a general lower bound on distortion of embedding µG
into an Euclidean space.
By the definition above,
|E|
F(µG ) = n 2
,
2 avg(µG )
where avg(µG2 ) is the average value of µG2 (i, j) over all pairs (i, j) of distinct vertices of G.
Consider now a Euclidean metric on V (G), δ ∈ `2 , namely, a metric of the form
δ (i, j) = kxi − x j k2 , xi i∈V (G) ⊂ Rm .
If F(δ ) is much larger than F(µG ) for every such δ , one immediately concludes that any such δ must
significantly distort µG . Formally,
Proposition 3.1.
dist2 (µG ,→ `2 ) ≥ min F(δ )/F(µG ) .
δ ∈`2
By a standard argument (see e. g., [13], Sect. 15.5), the minimum of F(δ ) over all such δ is precisely
γG /n , where γG is the spectral gap of G, that is, (d − λG ) where λG is the second largest eigenvalue of
the adjacency matrix of G. Thus, Proposition 3.1 implies,
Proposition 3.2.
n − 1 γG
dist2 (µG ,→ `2 ) ≥ · · avg(µG2 ) .
n d
In particular,
Corollary 3.3. Let {Gn } be a family of regular graphs; assume Gn has n vertices and degree dn . Suppose
the normalized spectral gaps γGn /dn are bounded away from zero and avg(µG2 n ) = Ω(log2 n). Then the
distance metric for this family of graphs is hard.
In what follows we shall deal with families of graphs for which avg(µG2 ) = Ω(Diam(G)2 ). We note
that, in particular, any vertex-transitive graph has this property. A graph is vertex-transitive if all of its
vertices are equivalent under automorphisms.
Proposition 3.4. If G is a vertex-transitive graph then avg(µG2 ) ≥ Diam(G)2 /8.
Proof. Indeed, let r be the smallest radius such that the corresponding r-ball in µG contains more than
n/2 vertices. Clearly, avg(µG2 ) ≥ r2 /2, while Diam(G) ≤ 2r .
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 127
I. N EWMAN , AND Y. R ABINOVICH
Therefore, for vertex-transitive graphs, it suffices to ensure a constant normalized spectral gap and
an Ω(log n) lower bound on the diameter.
Turning to Cayley graphs, it is well known that for (some) classes of non-Abelian groups, there
exist Cayley graphs with a bounded number of generators, and a constant spectral gap (see, e. g., [8],
the section on Cayley expander graphs). Since the constant number of generators guarantees that the
diameter is Ω(log n), this yields a graph as required in Corollary 3.3. (This is precisely the construction
used in [11, 3]). For Abelian groups such construction is impossible, since in order to ensure a constant
normalized gap γG /d, the number of generators must be at least Ω(log n) (see, e. g., [8]). This might
seem to be a problem, since, at least for general groups, that many generators may well cause the
diameter to be O(log n/ log log n) = o(log n). For Abelian groups, however, this does not happen! While
the following simple fact is well known (see, e. g., [8], proof of Prop. 11.5), it has apparently been
overlooked in the context of hard metrics.
Let h(p) = −p log2 p−(1− p) log2 (1− p) be the binary entropy function. For an Abelian group H, a
set A ⊆ H is called symmetric if A = −A (we use the additive notation for the Abelian group operation).
Proposition 3.5. Let H be an Abelian group of order n, and let A ⊂ H be a symmetric set of generators
of size d = c0 log2 n. Then, for any constant c1 such that (c0 + c1 ) · h(c1 /(c0 + c1 )) < 1, the diameter of
the corresponding Cayley graph G(H, A) is ≥ c1 log2 n for a large enough n.
The proposition follows from the observation that the number of distinct endpoints of paths of length
l in G starting at any (fixed) vertex is at most d+l
l , since due to commutativity of G it is at most the
number of partitions of a set of l identical elements to d (distinct) parts. Therefore, the number of points
reachable by a path of length ≤ c1 log2 n from a fixed vertex is at most
c1 log2 n
c0 log2 n + l h
c1
·(c0 +c1 )·log2 n
∑ ≤ 2 c0 +c1
=
l=0 l
c1
(c +c1 )·h
n 0 c0 +c1
< n.
Thus, as long as the number of generators is O(log n), our only concern is getting a constant normal-
ized spectral gap γG /d. This is summed up in the following theorem.
Theorem 3.6. Let us fix an arbitrary constant c0 > 0. Let H be an Abelian group of order n, let A ⊂ H be
a symmetric set of generators of size d = c0 log2 n and let G(H, A) be the corresponding Cayley graph.
If the normalized spectral gap γG /|A| = Ω(1), then µG is a hard metric.
It is well known that random choice achieves constant spectral gap (see, e. g., [1], in particular the
section on Abelian groups):
Proposition 3.7. Let H be an Abelian group of order n, and let A ⊂ H be a random symmetric set of
generators of size d = c0 log2 n for a suitable universal constant c0 (100 would certainly suffice). Then,
the corresponding Cayley graph G(H, A) almost surely has a normalized spectral gap ≥ 0.5.
For an efficient deterministic construction of such sets A (for any group, not only Abelian groups)
see [15, Sec. 5]. Combining Theorem 3.6 and Proposition 3.7, we arrive at the main result of this
section:
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 128
H ARD M ETRICS F ROM C AYLEY G RAPHS O F A BELIAN G ROUPS
Theorem 3.8. Let G = G(H, A) be a Cayley graph obtained by taking a random symmetric set of gener-
ators A ⊂ H of size d = c0 log2 |H| for a suitable universal constant c0 . Then, the shortest-path metric
of G is almost surely a hard metric.
Remark: Using the linear projective form
∑(i, j)∈E(G) ∆(i, j)
F1 (∆) =
∑i< j∈V (G) ∆(i, j)
instead of F(∆), implies the following for negative type metrics,
dist(µG ,→ NEG) ≥ min F1 (δ )/F1 (µG ) .
δ ∈NEG
Arguing along the same lines as for Euclidean metrics (and recalling that a metric in NEG is a square
of an `2 metric), it can be seen that the metrics of Theorem 3.8 are hard with respect to NEG as well.
4 When the Group is Zn2
In this case the group is just an n-dimensional vector space over Z2 . Any set of generators (vectors)
A is automatically symmetric. Following the requirements of Corollary 3.3, we have to ensure two
conditions: a constant normalized spectral gap and Ω(n) diameter.
The construction is based on good linear codes. Let C ⊂ Zm
2 be a linear code (subspace) of dimension
n. The weight w(v) of a vector v is the number of nonzero entries of v. The distance D(C) of C is the
minimum weight of nonzero vectors in C. C is said to be of linear distance if D(C) = Ω(m). In addition,
if n = Ω(m) the code is said to have a constant rate.
Let M be an n × m matrix whose rows form a basis for C (such an M is called the generator matrix
of C).
Proposition 4.1. Let C ⊂ Zm2 be a linear code. Let M be the corresponding n × m matrix and A the set
of columns of M as above. Then the spectral gap of the Cayley graph G = G(Zn2 , A) is γG = 2D(C).
It follows that the normalized spectral gap γG /m is bounded away from zero if and only if C is a
code of linear distance.
The proposition is folklore (see e. g. [1], proof of Proposition 2). Here is a sketch of the proof.
Proof. The characters {χu } of Zn2 , indexed by the group elements u ∈ Zn2 , are of the form
χu (x) = (−1)hu,xi ,
where the inner product is mod 2. Let A ⊂ Zn2 , |A| = m, be a set of generators (vectors), and let MA be
an n × m matrix over Z2 whose columns are the vectors of A. Keeping in mind that the eigenvectors of
G(Zn2 , A) are the characters, we conclude that the second largest eigenvalue λG of G(Zn2 , A) is
∑ (−1)hu,ai = u∈Zmax m − 2w(uT MA ) .
λG = max
n n
u∈Z \{0}
2 a∈A \{0}2
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 129
I. N EWMAN , AND Y. R ABINOVICH
Let C ⊆ Zn2 be a linear code generated by MA , that is, all linear combinations of the rows of MA . Then
C = {uT MA }u∈Zn2 ⊂ Zm 2 and hence λG = m − 2D(C). Since γG = m − λG , it follows that γG = 2D(C).
Therefore, γG = Ω(m) if and only C is a linear code of linear distance.
It remains to ensure that the diameter of G(Zn2 , A) is Ω(n). By Proposition 3.5, this condition will
necessarily hold provided m = O(n), that is, if C is of constant rate. We thus proved the following.
Theorem 4.2. Let C be a linear code of constant rate and linear distance, and dim(C) = n. Let M be an
n × m matrix whose rows form a basis for C, and let A ⊂ Zn2 be the set of columns of M. Then the metric
of G(Zn2 , A) is hard.
Linear codes of constant rate and linear distance have received considerable attention. Their exis-
tence has been established by numerous randomized and deterministic efficient constructions, with the
first explicit construction due to Justesen [9] (cf. [12]).
We conclude this section with a comparison of the construction of hard metrics due to Khot and
Naor [10] and our construction. Let C ⊂ Zm 2 be a linear code of constant rate and linear distance, of
dimension n. Let C be the dual code, i. e., C⊥ = {u | Mu = 0} where M is the generator matrix of C.
⊥
2 by x ≡ y if (x − y) ∈ C . Now, let X be a quotient metric space of
Define an equivalence relation on Zm ⊥
m
Z2 equipped with the Hamming metric, with respect to ≡. That is, the distance between two points a
and b in X is the Hamming distance between the two corresponding cosets A, B ⊂ Zm 2 . Khot and Naor
show that X with the induced metric is hard.
Proposition 4.3. The above construction is isometric to the construction described in Theorem 4.2.
Proof. Let M be a matrix as in Theorem 4.2. Then X can be viewed as the image of Zm 2 under the
linear mapping φ : Zm2 → Z n , φ (x) = Mx. Define the edges of X as the images of Hamming edges of Zm
2 2
under φ . Clearly, the quotient metric of X is precisely the shortest-path metric of the resulting graph.
The images of the Hamming edges are, however, precisely the column vectors of M, and the isometry
follows.
5 Additional Remarks
The constructions of Cayley graphs with hard shortest-path metric as described in Theorem 3.8 and
Theorem 4.2, yield graphs of degree logarithmic in the number of vertices. It is natural to ask whether
this must hold for all Cayley graphs of Abelian groups that induce a hard metric. Here we partially
answer this question and show that the degree can be anything between Ω(log n) and O(n1−ε ) for any
fixed 1 > ε > 0.
We start with the following simple fact:
Proposition 5.1. Let H be an Abelian group, and let m < |H| be a natural number. Then, there exists a
symmetric set B ⊆ H of size Θ(m) such that for every natural r the size of rB = {∑ri=1 bi | bi ∈ B} is at
most r · |B|.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 130
H ARD M ETRICS F ROM C AYLEY G RAPHS O F A BELIAN G ROUPS
Proof. Any finite Abelian group is a direct product of cyclic groups. Let H = C1 × C2 × . . . × Ct , and
assume that s j = |C1 | · |C2 | · . . . · |C j | < m, while s j+1 = |C1 | · |C2 | · . . . · |C j | · |C j+1 | ≥ m. Let a be a
generator of C j+1 . Define K j+1 = {i · a | i ∈ [−k, k] ⊂ N} where k is the smallest natural number such
that s j · (2k + 1) ≥ m. Finally, define B = C1 ×C2 × . . . ×C j × K j+1 × {0} × {0} × . . . It is easy to verify
that B has the required properties.
Theorem 5.2. Let H be an Abelian group of order n, and let 1 > ε > 0 be fixed. Then there exists a
symmetric set of generators, A, of size Θ(n1−ε ), such that the metric µG of the Cayley graph G = G(H, A)
is hard.
Proof. Let G0 = G0 (H, A) be a Cayley graph as in Theorem 3.8 (or Theorem 4.2), with |A| = c0 log2 n.
Assume for simplicity that A is augmented by {0}. Let B ⊆ H be as in Proposition 5.1 with m = n1−ε .
We claim that the Cayley graph G = G(H, A ∪ B) has the desired properties. To see that, we employ the
Poincaré form F 0 (∆) similar to F(∆) of (3.1), where in the numerator we use the edges of G0 instead of
the edges of G. Arguing as in Proposition 3.2, we conclude that
n − 1 γG0
dist2 (µG ,→ `2 ) ≥ · 0 · avg(µG2 ) . (5.1)
n d
We already know that the normalized spectral gap of G0 is constant. Thus, it will suffice to show that
the diameter of G is logarithmic. A closer examination of the proof of Proposition 3.5 reveals that
the number of distinct endpoints of paths of length ≤ cε/2 log2 n starting at a fixed vertex in G0 , is at
most nε/2+o(1) , provided that (c0 + cε/2 ) · h(cε/2 /(c0 + cε/2 )) ≤ ε/2. Therefore, the number of points
reachable by a path of length at most r = cε/2 log2 n in G is
|r · {A ∪ B}| ≤ |rA| · |rB| ≤ |rA| · r|B| ≤ nε/2 · n1−ε · Θ(no(1) ) < n .
(At most r rather than exactly r since both A and B contain 0.) Thus, the diameter of G is at least
cε/2 log2 n. This concludes the proof.
The last issue we would like to address in this paper is the following. As the proof of Theorem 5.2
shows, the hardness of µG can be deduced from the hardness of µG0 , where G0 is a sparse subgraph of
G. It is natural to ask whether the hardness of µG itself, where G is constructed as in Theorem 3.8, can
also be traced to a simple hard subgraph G0 of G. What is the “core” of the hardness? It turns out that G
does indeed contain such a subgraph! To avoid technicalities, we bring here only a broad outline of the
argument.
First, a purely graph-theoretic argument implies the following.
Proposition 5.3. G contains as a subgraph an expander of a bounded degree (say ≤ 500) and size Ω(n).
Indeed, by the Cheeger Inequality for graphs (cf. [8]), which relates the normalized spectral gap to
the normalized edge-expansion, G has edge expansion ≥ d/4 where d is the degree of G. Choosing each
edge of G independently at random with probability 100/d, we obtain a graph G̃ which almost has the
required properties. Recall that d is large enough (≈ 100 log n), and hence, by a Chernoff bound, almost
surely all sufficiently large subsets of vertices S, say |S| ≥ n/4, will have an edge-boundary of size at
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 131
I. N EWMAN , AND Y. R ABINOVICH
least c2 · 100 · |S| in G̃, for some constant c2 (e. g., c2 = 1/8 suffices). Let D be the set of all vertices
of degree more than 500. By Chernoff, this set is of size at most 10−100 · n and has edge boundary of
size at most 10−50 n. Thus, in G00 = G̃ − D all sets S of vertices, of size, say |S| ≥ n/3, will have an
edge-boundary of size at least c3 · 100 · |S|, where c3 could be taken to be, e. g., 1/9. Next, remove one
by one the subsets of vertices U that have fewer than c3 · 100 · |S| outgoing edges in the remaining part of
the graph. Since the union W of all removed has fewer than c3 |W | outgoing edges, we conclude that the
size of W is at most n/3. Thus, the graph G0 = G00 \W is almost surely a subgraph of G of size ≥ n/2,
degree ≤ 500, and edge expansion ≥ c3 · 100. Of course, G0 is not a Cayley graph anymore, it is not even
regular.
Finally, having such a large subgraph G0 in G implies the hardness of µG as asserted by the following
proposition.
Proposition 5.4. The existence of such G0 , combined with the property of G (as in Proposition 3.5), that
the radius of a µG -ball of size nΩ(1) in G is at least Ω(log n), implies the hardness of µG .
Indeed, let µ 0 denote the restriction of µG to V (G0 ). The hardness of µ 0 can be proved by employing
the Poincaré form FG0 (∆) as in Equation (3.1), and using the expansion of G0 to get, via the Cheeger
Inequality for graphs, a lower bound on the first eigenvalue of the Laplacian of G0 .
Now, using the same form FG0 (∆) as in Equation (3.1), this time for µG , we conclude that the square
avg(µ 2 )
of the distortion of µG is at least dist2 (µG0 ,→ `2 ) · avg(µ 2G ) . Since both avg(µG2 ), avg(µG2 0 ) are Θ(log2 n),
G0
the hardness of µG follows.
We end with the following open problem concerning hard metrics. In all previous constructions, as
well as in the current ones, the metrics that are constructed are hard with respect to NEG and hence with
respect to `1 and `2 . Is there a family of hard metrics that is hard with respect to `2 but not with respect
to NEG ?
References
[1] N. A LON AND Y. ROICHMAN: Random Cayley graphs and expanders. Random Structures Algo-
rithms, 5(2):271–284, 1994. [doi:10.1002/rsa.3240050203]. 128, 129
[2] S. A RORA , J. R. L EE , AND A. NAOR: Euclidean distortion and the sparsest cut. In Proc. 37th
STOC, pp. 553–562. ACM Press, 2005. [STOC:1060590.1060673]. 126
[3] Y. AUMANN AND Y. R ABANI: An O(log k) approximate min-cut max-flow theorem and approx-
imation algorithm. SIAM J. Comput., 27(1):291–301, 1998. [doi:10.1137/S0097539794285983].
126, 128
[4] J. B OURGAIN: On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math.,
52(1-2):46–52, 1985. 125
[5] S. C HAWLA , A. G UPTA , AND H. R ÄCKE: Embeddings of negative-type metrics and an im-
proved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):1–18, 2008.
[doi:10.1145/1361192.1361199]. 126
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 132
H ARD M ETRICS F ROM C AYLEY G RAPHS O F A BELIAN G ROUPS
[6] M. M. D EZA AND M. L AURENT: Geometry of Cuts and Metrics. Springer Verlag, 1997. 126
[7] A. G UPTA , R. K RAUTHGAMER , AND J. R. L EE: Bounded geometries, fractals, and low-distortion
embeddings. In Proc. 44th FOCS, pp. 534–543. IEEE Comp. Soc. Press, 2003. 126
[8] S. H OORY, N. L INIAL , AND A. W IGDERSON: Expander graphs and their applications. Bull.
Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]. 128, 131
[9] J. J USTESEN: A class of constructive asymptotically good algebraic codes. IEEE Trans. Inform.
Theory, 18(5):652–656, 1972. 130
[10] S. K HOT 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]. 126, 130
[11] N. L INIAL , E. L ONDON , AND Y. R ABINOVICH: The geometry of graphs and some of its algo-
rithmic applications. Combinatorica, 15(2):215–245, 1995. [doi:10.1007/BF01200757]. 126, 127,
128
[12] F. J. M AC W ILLIAMS AND N. J. A. S LOANE: The Theory of Error-Correcting Codes. North
Holland, 1977. 130
[13] J. M ATOU ŠEK: Lectures on Discrete Geometry. Springer, 2002. 127
[14] S. R AO: 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]. 126
[15] AVI W IGDERSON AND DAVID X IAO: Derandomizing the Ahlswede-Winter matrix-valued Cher-
noff bound using pessimistic estimators, and applications. Theory of Computing, 4(1):53–76, 2008.
[doi:10.4086/toc.2008.v004a003]. 128
AUTHORS
Ilan Newman
Department of Computer Science
Haifa University, Haifa, 31905, Israel
ilan@cs.haifa.ac.il
http://cs.haifa.ac.il/∼ilan
Yuri Rabinovich
Department of Computer Science
Haifa University, Haifa, 31905, Israel
yuri@cs.haifa.ac.il
http://cs.haifa.ac.il/∼yuri
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 133
I. N EWMAN , AND Y. R ABINOVICH
ABOUT THE AUTHORS
I LAN N EWMAN has been on the faculty at Haifa University since 1992. He obtained his
B. S. and M. S. at the Technion. He received his Ph. D. in 1992 at the Computer Science
Department of the Hebrew University under the supervision of Avi Wigderson. The
title of his thesis was “On the complexity of simple Boolean functions.” His current
research interests are in finite metric embeddings, combinatorial algorithms, property
testing, and computational complexity.
Born in Odessa, Ukraine, Y URI R ABINOVICH received his Ph. D. in 1993 from the Hebrew
University under the supervision of Avi Wigderson and Nati Linial. The title of his thesis
was “Theoretical properties of genetic algorithms.” Currently he works at the Computer
Science Department of Haifa University. He is interested in geometric phenomena in
discrete structures in general, and in the theory of finite metric spaces in particular.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 125–134 134