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

AF：小：几何不等式、聚类难度和社会选择

• 批准号: 1911216
• 负责人: Steven Heilman
• 金额: $ 9.03万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1911216&HistoricalAwards=false
• 关键词: AF; Small; Geometric; Inequalities; Clustering; AF; Small; Geometric; Inequalities; Clustering

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.

该项目试图回答以下相关问题：（1）“在计算机上群集数据的最佳方法是什么？” （2）“我们如何设计其成果在计数中不准确的稳健性的投票系统？” 例如，当内容提供商希望将具有相似兴趣的消费者聚集到单独的群体中时，出现问题（1）。 问题（2）在设计对第三方尝试干扰有弹性的投票系统时会出现。 问题（1）和（2）可以作为等级问题重新校正。等等问题的一个例子要求固定区域最多的固定长度的形状（答案是圆形栅栏，自古以来就已经知道了）。 在过去的二十年中，理论计算机科学的调查使问题（1）和（2）引起了人们的兴趣。 一般而言，理论计算机科学为计算机找到了尽快和高效地解决问题的方法。 该项目的总体目标是证明，与某些众所周知的有效算法相比，某些重要的计算问题无法更好地解决。该项目继续研究者对变体技术的应用来证明等等不平等现象。 这些不平等意味着计算硬度导致了社会选择理论中的理论计算机科学和最佳陈述。 理论计算机科学中的几个近期等等问题，例如（1）和（2）要求欧几里得集合最小的高斯表面积和固定的高斯体积。 自2012年的冷水和微型浴缸的具有里程碑意义的结果以来，很明显，变化技术可以解决这些等等问题，而其他方法未成功。 首席研究人员将继续采用冷水和微型浴缸的方法，以最终证明某些半决赛编程算法是假设Khot独特的游戏的猜想，这是几个感兴趣的问题的最好的近似算法。 预期的项目成果包括：最大 - cut问题的尖锐计算硬度结果，机器学习中的内核群集问题以及独特游戏的某些情况。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来通过评估来支持的。