权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

项目摘要

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)要求最小高斯表面积和固定高斯体积的欧几里得集合。自从Colding和Minicozzi在2012年取得里程碑式的成果以来，变分演算技术显然可以解决这些等周问题，而其他方法则无法成功。首席研究员将继续应用Colding和Minicozzi的方法，以最终证明某些半确定规划算法是几个感兴趣的问题的最佳逼近算法，假设Khot的唯一游戏猜想。预期的项目成果包括尖锐的计算硬度结果：MAX-m-CUT问题，机器学习的核聚类问题，以及独特游戏猜想的某些情况。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。