The line between mathematics and theoretical computer science is blurry, but for some the distinction doesn’t exist at all. The Simons Collaboration on Algorithms and Geometry, which launched in September 2014, brings together mathematicians and computer scientists who work on a variety of questions at the interface of the two disciplines. Despite the fact that this collaboration has only been up and running for a few months, it has already helped some researchers draw unexpected connections between seemingly disparate problems.
This new method for clustering data points into k clusters produces values between 0 and 1 for all pairs of points. These values express the likelihood that both points in the pair are in the same cluster. When data can be partitioned into k clusters with a value of 1 for all pairs inside the same cluster, and a value of 0 for all pairs of points across different clusters, the solution is optimal.
Amit Singer, an applied mathematician at Princeton University, is using cryo-electron microscopy (cryo-EM) to determine the structure of various biologically important molecules. The pictures produced by cryo-EM are noisy, two-dimensional projections taken from random directions. The computational challenge is to determine, from these two-dimensional images, their three-dimensional orientations and the configuration of the molecule pictured.
At first glance, this question would not seem to have much to do with, for example, the unique games conjecture, a problem in theoretical computer science originally formulated by fellow collaboration member Subhash Khot, winner of the 2014 Rolf Nevanlinna Prize. The unique games conjecture says that a certain problem in graph theory is difficult not only to solve but even to approximate efficiently, and has deep implications for other questions in theoretical computer science.
Singer reports that with the help of collaborator Moses Charikar, he realized that one of the algorithms that came from his research in cryo-EM was related to the unique games conjecture. “It’s a very interesting connection between a very applied problem in structural biology all the way to a very abstract problem in theoretical computer science.”
The collaboration is focused on problems and algorithms that transcend specific applications — and even the constraints of modern computing power. For example, given a collection of objects, with an inherent notion of ‘distance’ between any two of them, can one store them efficiently so that one could quickly determine which objects are the most similar to others? This question, called the nearest neighbor search, comes up in many guises and applications, from storing images and music to studyinghow different proteins work. “We’re interested in the foundations,” collaboration director Assaf Naor says. “We want to come up with general mathematical theorems that will apply to certain specific datasets, but also, when something new comes up, we want to have an arsenal to attack it with.”
Naor says the collaboration is currently in the “get to know you” phase, with researchers ramping up with in-depth presentations on their work. After that phase concludes, meetings will become increasingly focused on making progress on specific topics.
