RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

Saint John'S University, Jamaica NY

Investigators

Abstract

This project deals with embeddings of finite sets into spaces with well-understood geometry. Such embeddings form a well-established tool in theoretical computer science. Their usefulness can be seen in the following example: Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance (degree of dissimilarity) of its elements. One of the useful approaches to analysis of such sets of data is to use some low-distortion embeddings of the set into a space whose structure is well-known, for example into a two-dimensional or three-dimensional space. One can subsequently employ algorithms available in computational geometry and tools from classical mathematics. In some cases one can even visualize the structure of the set, for example, see its clusters. Another application of embeddings is to construction of approximate algorithms in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (consume too much time) and we seek not necessarily the optimal solution, but a solution that is close (in some sense) to being optimal. In many cases the best known approximate algorithms are based on metric embeddings. The project aims to deepen understanding in this important area. The main goal of the proposal is to study embeddings of discrete metric spaces into Banach spaces. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, for example for applications in topology, weaker types of embeddings are useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important insights. This project will contribute to the following general question: Find new classes of embeddings of finite and locally finite metric spaces into Banach spaces and find new types of obstructions to such embeddings. The three main directions of the work are: (1) determine to what extent expanders and graphs with large girth resist nontrivially good embeddings; (2) find characterizations of well-known classes of Banach spaces in terms of embeddings; and (3) analyze structures that create obstructions to coarse embeddings of spaces with bounded geometry into a Hilbert space. The project is expected to employ a mixture of methods of geometric functional analysis and graph theory, with some use of methods of probability theory and geometric group theory.