Isoperimetric Clusters and Related Extremal Problems with Applications in Probability

平面的等周问题——人们已经知道并研究了2000多年——问的是给定区域的哪种形状的周长最小（答案是：一个圆）。在过去的一百年里，我们在两个方向上取得了重大的进展和推广：一方面，我们现在如何研究其他空间上的相关问题，包括球面、双曲空间和高斯空间。另一方面，在某些情况下，我们可以描述当我们同时优化多个集合时会发生什么。特别是，我们可以描述当肥皂泡接触时会发生什么，这也让我们深入了解泡沫的结构。令人惊讶的是，这些几何问题与计算复杂性有着密切的联系：人们普遍认为许多重要的计算问题无法有效地解决。更重要的是，对于应用程序（因为在实践中我们通常不需要精确的解决方案），甚至在计算上也很难近似地解决其中一些问题。研究这一主题的领域，被称为“近似的硬度”，在过去的二十年里取得了突飞猛进的进展，其开创性的成就之一是在计算复杂性和几何和概率论中的等周型问题之间建立了深刻的联系。如果我们对某些概率性的、高维的、多部分的等周问题有了更好的理解，就可以解决近似硬度方面的几个开放性问题。该项目还将开发数值计算软件，并为学生提供建议和指导。这个项目是关于引入和开发多部分等周问题的新技术，重点是几何中的自然问题（如球体上的双泡猜想）和来自计算机科学的问题。这些划分问题的困难之一是存在组合的许多鞍点或局部最小值，但研究者最近（与E. Milman）的高斯双泡猜想的解决方案包括一种新的方法来绕过这个困难；PI将在此成功的基础上，将该方法扩展到相关设置。该项目将允许研究生和本科生参与相关的研究项目，它将帮助开发用于数值计算的开源软件，并将支持K-12学生的外展活动。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.