Algorithmic High-Dimensional Geometry

Lecture 1: Algorithmic High-Dimensional Geometry I
Lecture 2: Algorithmic High-Dimensional Geometry II
 

This series of talks was part of the Big Data Boot Camp. Videos for each talk are available through the links above.

Speaker: Alexandr Andoni, Microsoft Research

For many computational problems, it is beneficial to see them through the prism of high-dimensional geometry. For example, one can represent an object (e.g., an image) as a high-dimensional vector, depicting hundreds or more features (e.g., pixels). Often direct or classical solutions to such problems suffer from the so-called "curse of dimensionality": the performance guarantees tend to have exponential dependence on the dimension. Modern tools from high-dimensional computational geometry address this obstacle.

These lectures will give an overview of some key problems and tools in the area, including nearest neighbor search, dimensionality reduction, embeddings and intrinsic dimension, and may touch upon some connections to related areas, such as sublinear algorithms.