TOC Seminar: A Metric Notion of Dimension and its Algorithmic Applications
Speaker: Robert Krauthgamer , IBM
Date: December 8 2004
Time: 4:15PM to 5:00PM
Location: Room 32-G449 (Kiva)
Contact: Santosh Vempala, vempala@math.mit.edu
Relevant URL:
Abstract:
Let us define the dimension of a metric space to be the minimum k>0 such
that every ball in the metric space can be covered by 2^k balls of half
the radius. This definition, which is applicable to every metric space
has several attractive features. For instance, it coincides with the
standard notion of dimension in Euclidean spaces, but captures also
nonlinear structures such as manifolds.
I will survey some recent results dealing with metric spaces of low
dimension (under the above definition). This includes embeddings into
low-dimensional Euclidean spaces, as well as algorithms for computational
problems involving metric spaces, such as Nearest Neighbor Search and the
Traveling Salesmen Problem.
See other events that are part of
See other events happening in December 2004
