CAREER: Geometric Frontiers in Algorithm Design

点击翻译按钮获取中文摘要

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.