This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in [8]). We then proceed to construct optimal Ramsey partitions, and use them to show that for every ε ∈ (0, 1), every n-point metric space has a subset of size n 1−ε which embeds into Hilbert space with distortion O(1/ε). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in [32]. Namely, we show that for every n point metric space X, and k ≥ 1, there exists an O(k)-approximate distance oracle whose storage requirement is O n 1+1/k , and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking. Motivated by the search for a non-linear version of Dvoretzky's theorem, Bourgain, Figiel and Milman [8] posed the following problem, which is known today as the metric Ramsey problem: Given a target distortion α > 1 and an integer n, what is the largest k such that every n-point metric space has a subset of size k which embeds into Hilbert space with distortion α? (Recall that a metric space (X, d X ) is said to embed into Hilbert space with distortion α if there exists a mapping f : X → L 2 such that for every x, y ∈ X, we have . This problem has since been investigated by several authors, motivated in part by the discovery of its applications to online algorithms -we refer to [5] for a discussion of the history and applications of the metric Ramsey problem. The most recent work on the metric Ramsey problem is due to Bartal, Linial, Mendel and Naor [5] , who obtained various nearly optimal upper and lower bounds in several contexts. Among the results in [5] is the following theorem which deals with the case of large distortion: For every ε ∈ (0, 1), any n-point metric space has a subset of size n 1−ε which embeds into an ultrametric with distortion O Since ultrametrics embed isometrically into Hilbert space, this is indeed a metric Ramsey theorem. Moreover, it was shown in [5] that this result is optimal up to the log(2/ε) factor, i.e. there exists arbitrarily large n-point metric spaces, every subset of which of size n 1−ε incurs distortion Ω(1/ε) in any embedding into Hilbert space. The main result of this paper closes this gap:  In the four years that elapsed since our work on [5] there has been remarkable development in the structure theory of finite metric spaces. In particular, the theory of random partitions of metric spaces has been considerably refined, and was shown to have numerous applications in mathematics and computer science (see for example [17, 25, 24, 1] and the references therein). The starting point of the present paper was our attempt to revisit the metric Ramsey problem using random partitions. It turns out that this approach can indeed be used to resolve the metric Ramsey problem for large distortion, though it requires the introduction of a new kind of random partition, an improved "padding inequality" for known partitions, and a novel application of the random partition method in the setting of Ramsey problems. In Section 2 we introduce the notion of Ramsey partitions, and show how they can be used to address the metric Ramsey problem. We then proceed in Section 3 to construct optimal Ramsey partitions, yielding Theorem 1.1. Our construction is inspired in part by Bartal's probabilistic embedding into trees [4] , and is based on a random partition due to Calinescu, Karloff and Rabani [9] , with an improved analysis which strengthens the work of Fakcharoenphol, Rao and Talwar [17] . In particular, our proof of Theorem 1.1 is self contained, and considerably simpler than the proof of the result from [5] quoted above. Nevertheless, the construction of [5] is deterministic, while our proof of Theorem 1.1 is probabilistic. Moreover, we do not see a simple way to use our new approach to simplify the proof of another main result of [5] , namely the phase transition at distortion α = 2 (we refer to [5] for details, as this result will not be used here). The results of [5] which were used crucially in our work [27] on the metric version of Milman's Quotient of Subspace theorem are also not covered by the present paper. Algorithmic applications to the construction of proximity data structures. The main algorithmic application of the metric Ramsey theorem in [5] is to obtain the best known lower bounds on the competitive ratio of the randomized k-server problem. We refer to [5] and the references therein for more information on this topic, as Theorem 1.1 does not yield improved k-server lower bounds. However, Ramsey partitions are useful to obtain positive results, and not only algorithmic lower bounds, which we now describe. A finite metric space can be thought of as given by its n × n distance matrix. However, in many algorithmic contexts it is worthwhile to preprocess this data so that we store significantly less than n 2 numbers, and still be able to quickly find out approximately the distance between two query points. In other words, quoting Thorup and Zwick [32], "In most applications we are not really interested in all distances, we just want the ability to retrieve them quickly, if needed". The need for such "compact" representation of metrics also occurs naturally in mathematics; for example the methods developed in theroetical computer science (specifically [11, 20] ) are a key tool in the recent work of Fefferman and Klartag [18] on the extension of C m functions defined on n points in R d to all of R d . An influential compact representation of metrics used in theoretical computer science is the approximate distance oracle [3, 14, 32, 20] . Stated formally, a (P, S , Q, D)-approximate distance oracle on a finite metric space (X, d X ) is a data structure that takes expected time P to preprocess from the given distance matrix, takes space S to store, and given two query points x, y ∈ X, computes in time Q a number E(x, y) satisfying In what follows we will depart from the above somewhat cumbersome terminology, and simply discuss D-approximate distance oracles (emphasizing the distortion D), and state in words the values of the other relevant parameters (namely the preprocessing time, storage space and query time). An important paper of Thorup and Zwick [32] constructs the best known approximate distance oracles. Namely, they show that for every integer k, every n-point metric space has a (2k − 1)-approximate distance oracle which can be preprocessed in time O n 2 , requires storage O k · n 1+1/k , and has query time O(k). Moreover, it is shown in [32] that this distortion/storage tradeoff is almost tight: A widely believed combi-
His approach was to start by invoking the Mendel and Naor REF distance oracle to obtain an initial distance estimation.
Ramsey partitions and proximity data structures
J. European Math. Soc. 9(2): 253-275, 2007
Computer Science Mathematics