CAREER: Geometric Frontiers in Algorithm Design

复杂的数据集出现在大量的应用程序领域中，包括各种物理过程的测量、金融交易的历史记录、网络中用户活动的日志等等。因此，对这些数据集的分析对科学和工程来说是一项日益重要的任务。尽管在许多应用程序中有大量这样的原始输入，但提取有意义的信息通常是一个主要的计算挑战。在大多数情况下，这种困难是由于缺乏数据的有用表示。近年来，几何方法已成为克服这一困难不可或缺的工具。这种发展背后的原因是，具有两两相似性的数据集可以自然地解释为几何空间。这些数据集包括DNA序列、统计分布、新闻文章集合等等。在这种解释下，几个重要的数据分析问题可以理解为几何计算问题。例如，分类问题可以表示为几何划分。类似地，将一个模型拟合到一组测量值的问题可以被认为是在一些适当的几何空间中的插值。在这些情况下，主要的算法挑战发生在高维，或者更一般地说，复杂的度量空间中。该项目旨在解决这些几何数据集分析中固有的一些主要问题，从而为各种计算任务提供改进的解决方案。该项目还寻求在几何数据分析中使用多种数学工具，在数学和计算机科学之间建立新的联系。拟议的研究将成为PI课程开发、本科和研究生教学以及教育和推广活动的一部分。它还将提供一套研究问题，用于指导本科生和研究生。

Complex data sets arise in a plethora of application domains from measurements of various physical processes, history of financial transactions, logs of user activity in a network, and so on. The analysis of such data sets is therefore a task of increasing importance for science and engineering. Even though in many applications there is an abundance of such raw inputs, extracting meaningful information can often be a major computational challenge. In most cases, this difficulty is due to the lack of a useful representation of the data.Over the recent years, geometric methods have become an indispensable tool for overcoming this difficulty. The reason behind this development is the fact that a data set endowed with pairwise similarities can be naturally interpreted as a geometric space. Such data sets include DNA sequences, statistical distributions, collections of news articles, and so on. Under this interpretation, several important data analytic questions can be understood as geometric computational problems. For example, the problem of classification can be expressed as geometric partitioning. Similarly, the problem of fitting a model to set of measurements can be thought of as interpolation in some appropriate geometric space.In these contexts, the main algorithmic challenges occur in high-dimensional, or more generally, complex metric spaces. This project aims at resolving some of the main problems inherent in the analysis of such geometric data sets, and thus enabling improved solutions for a variety of computational tasks. The project also seeks to use diverse mathematical tools in the setting of geometric data analysis, forging new connections between mathematics and computer science.The proposed research will be part of the PI's curriculum development, undergraduate and graduate teaching, and educational and outreach activities. It will also provide the set of research problems that will be used for mentoring undergraduate and graduate students.