Tata Institute of Fundamental Research
Bourgain's Theorem
Seminar
Speaker:
Rakesh Venkat
Organiser:
John Barretto
Date:
Friday, 9 Mar 2012, 15:00 to 16:30
Venue:
AG-69
(Scan to add to calendar)
Abstract:
Problems in Metric embedding involve mapping a set (for our purposes, finite) of points from one metric space to another, while preserving pairwise distances. Of late, this has attracted much research interest in computer science as a tool for designing approximation algorithms. We shall see the proof of a fundamental theorem due to Bourgain, which states that n points in *any* metric space on can be mapped into l_1 space (R^d with the l_1 norm between points), while increasing pairwise distances by a factor of at most O(log(n)).
| Speaker: | Rakesh Venkat |
| Organiser: | John Barretto |
| Date: | Friday, 9 Mar 2012, 15:00 to 16:30 |
| Venue: | AG-69 |
(Scan to add to calendar)
Abstract:
Problems in Metric embedding involve mapping a set (for our purposes, finite) of points from one metric space to another, while preserving pairwise distances. Of late, this has attracted much research interest in computer science as a tool for designing approximation algorithms. We shall see the proof of a fundamental theorem due to Bourgain, which states that n points in *any* metric space on can be mapped into l_1 space (R^d with the l_1 norm between points), while increasing pairwise distances by a factor of at most O(log(n)).