Abstract:

Geometric spaces arise in Computer Science in a number of ways; the 
input to a problem may be explicitly geometric, it may be beneficial to 
impose some geometry that wasn't present a priori, or the geometry can arise 
as a result of some optimization (e.g. in semi-definite programming).  
I will discuss a variety of such spaces--one in each of these contexts--and 
the relevant algorithmic problems, including metric spaces of small 
intrinsic dimension (near-neighbor search), negatively curved spaces (TSP), 
and sub-Riemannian manifolds (Sparsest Cut).  The presentation will be 
mostly informal and intuitive.