[Banach] Abstract of a paper by Manor Mendel and Assaf Naor

[Dale Alspach]

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 at 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 at arXiv.org.