AF: Small: Geometric Inequalities, Clustering Hardness, and Social Choice

这个项目试图回答以下相关问题：(1)“在计算机上聚集数据的最佳方式是什么？”(2)“我们如何设计投票系统，其结果在计票不准确的情况下是稳健的？”例如，当内容提供商想要将具有相似兴趣的消费者聚集到不同的组中时，问题(1)就会出现。问题(2)是在设计对第三方企图干涉有弹性的投票系统时出现的。问题(1)和(2)可以重新表述为等周问题。等周问题的一个例子是要求固定长度的栅栏的形状，该栅栏包围了最大的区域(答案是圆形栅栏，这是自古以来就知道的)。在过去的二十年里，理论计算机科学的研究重新引起了人们对问题(1)和(2)的兴趣。一般说来，理论上的计算机科学会找到让计算机尽可能快速高效地解决问题的方法。这个项目的首要目标是证明一些重要的计算问题不可能比一些著名的高效算法更好地解决。本项目继续研究人员应用变分技术来证明等周不等式。然后，这些不平等意味着理论计算机科学中的计算难度结果和社会选择理论中的最优化陈述。最近在理论计算机科学中的几个等周问题，如(1)和(2)要求最小的高斯表面积和固定的高斯体积的欧几里得集。自从2012年Colding和Minicozzi的一个里程碑式的结果以来，变分技术显然可以解决这些其他方法不成功的等周问题。主要研究人员将继续应用Colding和Minicozzi的方法，以最终证明某些半定规划算法是几个感兴趣的问题的最佳可能逼近算法，假设科特的唯一博弈猜想。预期的项目结果包括：Max-m-Cut问题，来自机器学习的核集群问题，以及独特的游戏猜想的某些案例。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project seeks to answer the following related questions: (1) "What is the best way to cluster data on a computer?" (2) "How can we design voting systems whose outcomes are robust in the face of inaccuracies in counting?" Question (1) arises, for instance, when a content provider wants to cluster consumers with similar interests into separate groups. Question (2) arises when designing voting systems that are resilient to attempted interference by third parties. Questions (1) and (2) can be reformulated as isoperimetric problems. One example of an isoperimetric problem asks for the shape of a fence of fixed length that encloses the most area (the answer being a circular fence, which has been known since ancient times). Investigations in theoretical computer science in the last two decades have given renewed interest for Questions (1) and (2). Generally speaking, theoretical computer science finds ways for computers to solve problems as quickly and as efficiently as possible. The overarching goal of this project is to prove that some important computational problems cannot possibly be solved better than by some well-known efficient algorithms.This project continues the investigator's application of calculus of variations techniques to prove isoperimetric inequalities. These inequalities then imply computational-hardness results in theoretical computer science and optimality statements in social-choice theory. Several recent isoperimetric problems in theoretical computer science such as (1) and (2) ask for the Euclidean sets of smallest Gaussian surface area and fixed Gaussian volume. Since a landmark result of Colding and Minicozzi in 2012, it has become apparent that calculus of variations techniques can solve these isoperimetric problems, where other methods are not successful. The principal investigator will continue to apply the methods of Colding and Minicozzi in order to ultimately prove that certain semidefinite programming algorithms are the best possible approximation algorithms for several problems of interest, assuming Khot's Unique Games Conjecture. Expected project outcomes include sharp computational hardness results for: the MAX-m-CUT problem, a kernel-clustering problem from machine learning, and certain cases of the Unique Games Conjecture.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.