This is an announcement for the paper "Ramsey partitions and proximity data structures" by Manor Mendel and Assaf Naor.

Abstract: 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 \cite{BFM86}). We then proceed to construct optimal Ramsey partitions, and use them to show that for every $\e\in (0,1)$, any $n$-point metric space has a subset of size $n^{1-\e}$ which embeds into Hilbert space with distortion $O(1/\e)$. This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor \cite{BLMN05}, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick in \cite{TZ05}. Namely, we show that for any $n$ point metric space $X$, and $k\geq 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.

Archive classification: Data Structures and Algorithms; Computational Geometry; Metric Geometry; Functional Analysis

The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size .

Submitted from: anaor@microsoft.com

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/cs.DS/0511084

or

http://arXiv.org/abs/cs.DS/0511084

or by email in unzipped form by transmitting an empty message with subject line

uget 11084

or in gzipped form by using subject line

get 11084

to: math@arXiv.org.