The Simons Collaboration on Algorithms and Geometry addresses fundamental questions at the interface of mathematics and theoretical computer science. It brings together a unique group of researchers from diverse backgrounds in pure and applied mathematics and in theoretical computer science. Investigators will focus on questions of computational hardness, on structural foundations of metrics and networks, and on data structures of geometric origin. In addition to investigating the basic structures central to a wide range of algorithmic questions, the Simons Collaboration on Algorithms and Geometry aims to create new mathematics, including the design of advanced algorithms based on new mathematical insights.
Goals
The core research topics include the following three interrelated categories:
• Continuous relaxations, isoperimetry and computational hardness
Isoperimetric questions ask for estimates on the size of the boundary of a body of a given volume in various geometric settings. Major developments in computer science over the last decade led to the realization that many of the most fundamental computational problems are intimately linked to such isoperimetric type questions. There are also remarkable links with classical mathematics, such as the characterization of the Grothendieck constant (1953) as the hardness ratio of a combinatorial problem. The grand challenge here is to use geometry to plot the boundary between the tractable and the intractable, an endeavor that requires new insights into both geometry and algorithms, and benefits both fields.
• Structural foundations of metrics and networks and their algorithmic applications
Metric spaces are fundamental mathematical objects of immense importance in numerous contexts. Outside pure mathematics, they are used to model networks, measure similarities between proteins and images and are extensively used in the design of algorithms. The Simons Collaboration on Algorithms and Geometry will focus on discovering foundational structural results on these key objects that could shed light on many algorithmic contexts. Such structural information will be harnessed for applications in pure mathematics as well as in algorithmic design. Some of the goals include discovering and applying decomposition results for metric spaces, existence of well-behaved subspaces and quotients, geometrically faithful realizations, formulation of new invariants, and impossibility results. These investigations are often motivated by an emerging dictionary that translates insights and concepts from structured continuous theories to the seemingly unstructured metric setting.
• Algorithms and data structures for problems of geometric origin
Many real-life data sets of interest are inherently geometric: images, point clouds and physical objects, such as those arising in the analysis of protein structure or computer tomography. Some of the main algorithmic problems arising in these applications include clustering, dimensionality reduction and nearest neighbor search.