Dvoretzky's Theorem in Metric Spaces
<-- Return to the list
Date: 10-02-2007
Start Time:
4:00pm
End Time: 5:00pm
Speaker: Assaf Naor, New York University
Location: 622 Math
ABSTRACT
For every є > 0, any n-point metric space has a subset of size n1−є which embeds into Hilbert space with distortion O( 1/є ). This result is optimal up to constant factors, and it thus completes the work on thenon-linear Dvoretzky problem which was posed by Bourgain, Figiel and Milman in 1986. Moreover, such a metric Ramsey theorem can be used to solve several problems in theoretical computer science. Much like the proof of the classical Dvoretzky theorem from convex geometry, the proofof this theorem is probabilistic. I will present a self contained proof of this result, and I will also mention the history of this problem and some of its algorithmic applications.Based on joint work with Manor Mendel.
BIO
For more information about Dr. Naor, please go to this site.