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

本项目旨在回答以下相关问题：（1）“在计算机上聚类数据的最佳方法是什么？“（2）“我们如何设计出在计票不准确的情况下结果仍然稳健的投票系统？“例如，当内容提供商希望将具有相似兴趣的消费者聚集到不同的群体时，就会出现问题（1）。 问题（2）出现在设计投票系统时，该系统对第三方的企图干扰具有弹性。 问题（1）和（2）可以转化为等周问题。等周问题的一个例子是要求一个固定长度的栅栏的形状，它包围了最大的面积（答案是圆形栅栏，自古以来就被称为）。 在过去的二十年里，理论计算机科学的研究重新引起了人们对问题（1）和（2）的兴趣。 一般来说，理论计算机科学为计算机找到尽可能快速和有效地解决问题的方法。 这个项目的首要目标是证明一些重要的计算问题不可能比一些著名的有效算法更好地解决。这个项目继续研究者的应用变分法技术证明等周不等式。 这些不等式意味着理论计算机科学中的计算困难结果和社会选择理论中的最优性陈述。 理论计算机科学中最近出现的几个等周问题，如（1）和（2），要求最小高斯表面积和固定高斯体积的欧几里德集。 自从2012年Colding和Minicozzi的一个里程碑式的结果以来，变分法技术可以解决这些等周问题，而其他方法并不成功。 主要研究者将继续应用Colding和Minicozzi的方法，以最终证明某些半定规划算法是几个感兴趣的问题的最佳近似算法，假设Khot的唯一游戏猜想。 预期的项目成果包括：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.