[Colloquium] Talk by Assaf Naor, Microsoft Research, Feb. 6
Margery Ishmael
marge at cs.uchicago.edu
Mon Jan 19 15:04:18 CST 2004
------------------------------------------------------------------------
---
DEPARTMENT OF COMPUTER SCIENCE - TALK
Date: Friday, February 6, 2004
Time: 2:30 p.m.
Place: Ryerson 251
------------------------------------------------------------------------
----
Speaker: ASSAF NAOR, Microsoft Research
Url: http://research.microsoft.com/research/theory/naor/
Title: How Well does a Metric Space Embed into a Normed Space?
Abstract: The problem of estimating the least distortion required to
embed a finite metric space into a normed space arose in the 1960s in
the local theory of Banach spaces. It turns out that several
fundamental geometric problems in Banach space theory can be
characterized in terms of the embeddability of certain classes of
finite metrics. Additionally, due to intensive investigations by
computer scientists in the past decade, it is now well understood that
embedding results into various normed spaces are a powerful tool in the
design of approximation algorithms. Bourgain has shown that every
n-point metric space embeds into Euclidean space with distortion O(log
n), and this bound is best possible without additional geometric
information. In this talk we will present refinements of this result
and describe related problems and techniques of modern embedding
theory.
*Refreshments will follow the talk in Ryerson 255*
People in need of assistance should call 773-834-8977 in advance.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 1759 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20040119/f210cb18/attachment.bin
More information about the Colloquium
mailing list