Bourgain's Theorem

by Mr Rakesh Venkat (School of Technology and Computer Science)

Friday 9 Mar 2012, 15:00 → 16:30 Asia/Kolkata

AG-69 (Colaba Campus)

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