When one needs to perform an algorithmic task on a large data set it is often the case that the best way to fathom the massive amount of information contained in the data is to visualize it geometrically. By representing the input as a geometric object one can observe certain helpful features, such as clusters or low-dimensional structures within the data, and harness this structural information to solve the algorithmic problem at hand. In recent years the geometric approach to the design of algorithms has been greatly enhanced by the use of powerful methods from modern mathematics. This research project is at the frontier both for mathematics and computer science. Using ideas from analysis and geometry, combined with modern algorithmic methods and intuitions, the investigator's study will lead to advances on central algorithmic primitives for a wide variety of tasks ranging from combinatorial optimization and machine learning to information retrieval and bioinformatics. The goal of this research is to embed data into a well understood geometric object (such as Euclidean space), so that certain essential features of it are preserved. This makes it possible to harness intuitions and methods that were not available before the embedding was performed. The investigator will develop new mathematical tools for the study of algorithms for partitioning and clustering large networks, techniques for dimensionality reduction, constructions of compact representations of data, and methods for fast similarity search and classification. The proposed research will be of interest to computational scientists in a broad range of areas. The connection between mathematics and computer science will be deepened in order to disseminate powerful new ideas for algorithm design. 1
