Bourgain's Theorem



Friday, 9 March 2012, 15:00 to 16:30


  • AG-69


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)).