Isoperimetric Clusters and Related Extremal Problems with Applications in Probability

The isoperimetric problem in the plane -- which has been known and studied for more than 2 millennia -- asks which shape of a given area has a minimal perimeter (the answer: a circle). The last hundred years have seen significant advances and generalizations in two directions: on one hand, we now how how to study related problems on other spaces including on the sphere, in hyperbolic space, and in Gaussian space.

On the other hand, in some situations we can describe what happens when we optimize multiple sets at the same time. In particular, we can describe what happens to soap bubbles when they touch, which also gives insight into the structure of foams. Surprisingly, these geometric problems have a close link to computational complexity: is it widely believed that many important computational problems cannot be solved efficiently.

More importantly for applications (because in practice we don't often need exact solutions), it's computationally hard even to approximately solve some of these problems. The field that studies this topic, known as "hardness of approximation," has progressed in leaps and bounds over the last two decades, and one of its seminal achievements was the forging of a deep connection between computational complexity and isoperimetric-type problems in geometry and probability.

If we had a better understanding of certain probabilistic, high-dimensional, multi-part isoperimetric problems, it would close several open problems in hardness of approximation. The project will also develop software for numerical computation and support the advising and mentoring of students.

This project is about introducing and exploiting new techniques for multi-part isoperimetric problems, with an emphasis on both problems that are natural in geometry (such as the double-bubble conjecture on the sphere) and problems coming from computer science. One of the difficulties with these partitioning problems is the presence of combinatorially many saddle points or local minima, but the investigator's recent resolution (with E.

Milman) of the Gaussian double-bubble conjecture included a new method to circumvent this difficulty; the PI will build on this success by extending the method to related settings. This project will allow graduate and undergraduate students to participate in related research projects, it will aid the development of open-source software for numerical computation, and it will support outreach activities for K-12 students.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.