CAREER: Geometric Phenomena in Algorithms and Complexity

University Of Washington, Seattle WA

Investigators

Abstract

This research involves the use of high-dimensional geometry in attacking problems at the forefront of computer science. This includes closing fundamental gaps in our understanding of theoretical issues, as well as solving practical problems that arise from the need to analyze and manipulate massive data sets. Such data sets arise naturally in disparate fields like machine learning, computer vision, and bioinformatics. On the foundational side, high-dimensional geometric techniques play a pivotal role in obtaining fast, approximate solutions to classical hard problems which are difficult to solve exactly. The investigator will study these connections and the development of new algorithmic techniques to exploit them. More specifically, the PI will seek new algorithms which provide better approximate solutions to a variety of classical problems in areas such as graph partitioning, data clustering, and graph coloring. Many of these approaches are based on semi-definite programming and an important goal of the project is to understand exactly the power that this class of algorithms provides, via both new algorithmic techniques and complexity-theoretic lower bounds. These endeavors will incorporate techniques from high-dimensional geometry and probability, functional analysis, and extremal combinatorics. Another goal concerns coping with the dimensionality of data sets. For this purpose, the goal is to develop both new dimension reduction techniques, as well as algorithms and data structure that are able to operate directly on intrinsic low-dimensional structures inside data whose representation is, a priori, high-dimensional.