Geometry has become a central notion in algorithm design, in fields as diverse as bioinformatics and graph partitioning. This research is a concerted and unified attack on a large subset of the underlying mathematical problems, which often have to do with geometric embeddings of finite metric spaces. The concrete applications range from clustering and learning to compact representation of data to graph partitioning to nearest neighbor searching. Since the research spans a a variety of fields, the assembled team is multidisciplinary, involving analysts (Johnson and Naor), a geometer (Gromov), a discrete mathematician and combinatorialist (Linial) and algorithm designers (Arora and Charikar).
The research area emerging from the ongoing geometrization of algorithms is an exciting new frontier for both mathematics and computer science. For example, deep mathematical results such as Lipschitz extension may turn out to have applications to the practical problem of compactly representing computer sounds. In turn, algorithmic settings provide a fertile new ground for mathematical theory. The investigators study geometric representations for data and low disortion mappings into structured spaces. Metrics that arise in the design of approximation algorithms for NP-hard problems are studied, especially to understand their local versus global properties. The research develops new understanding for practically important metrics such as earth mover and edit distance metrics, which are defined in terms of computational effort and have thus not been studied in mathematics.
