CAREER: Learning, testing, and hardness via extremal geometric problems

职业：通过极值几何问题学习、测试和硬度

基本信息

批准号：
2145800
负责人：
Joseph Neeman
金额：
$ 40.75万
依托单位：
University of Texas at Austin
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-06-01 至 2023-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2145800&HistoricalAwards=false
关键词：
CAREER Learning testing hardness via

项目摘要

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).If P differs from NP, there are many important computational problems that cannot be solved efficiently. Even more importantly for applications (because in practice exact solutions are often not needed), it is 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. One of the seminal achievements of the field was the forging of a deep connection between computational complexity and isoperimetric-type problems in geometry and probability. The isoperimetric problem in the plane -- which has been known and studied for more than 2 millenia -- asks which shape of a given area has a minimal perimeter (the answer: a circle). If there were a better understanding of certain probabilistic, high-dimensional variants of this problem, it would close several open problems in hardness of approximation. A better understanding of the limits of efficient approximate computation will in turn lead to better algorithms for real-world computational problems.This project is about strengthening the link between hardness of approximation, geometry and probability. By solving new optimal partitioning problems in geometry and probability, the investigator will develop algorithms and prove new algorithmic hardness results. 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. Algorithmic consequences of these optimal partitioning problems include (i) improved bounds for testing and learning geometric concept classes; (ii) improved algorithms for non-interactive correlation distillation (a problem in cryptography with applications to random beacons and information reconciliation); and (iii) a stronger separation between classical and quantum communication complexity. This award will allow graduate and undergraduate students to participate in related research projects, it will fund 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.

该奖项是根据2021年《美国救援计划法》的全部或部分资助（公共法117-2）。如果P与NP不同，则有许多重要的计算问题无法有效解决。更重要的是，对于应用程序（实际上通常不需要精确的解决方案），即使大约解决其中一些问题，在计算上也很难。在过去的二十年中，研究该主题的领域被称为“近似硬度”。该领域的开创性成就之一是在几何学和概率中锻造计算复杂性与等级类型问题之间的深厚联系。平面中的等等问题（已知和研究超过2毫米）询问给定区域的哪个形状的周长最小（答案：一个圆圈）。如果对该问题的某些概率，高维变异有更好的了解，它将解决近似硬度的几个开放问题。对有效近似计算的限制的更好理解反过来又导致了现实世界中计算问题的更好算法。该项目是关于加强近似，几何和概率的硬度之间的联系。通过解决几何和概率中的新最佳分区问题，研究者将开发算法并证明新的算法硬度结果。这些分区问题的困难之一是组合上存在许多马鞍点或局部最小值，但是研究者最近对高斯双重气泡的猜想的解决方案（与E. Milman）的解决方案包括一种新方法来解决这一困难。这些最佳分区问题的算法后果包括（i）改进测试和学习几何概念类别的范围；（ii）改进了非相关性蒸馏的算法（密码学的问题与随机信标和信息核对的应用）；（iii）经典和量子通信复杂性之间的分离更强。该奖项将使研究生和本科生能够参与相关研究项目，它将为开源软件的开发用于数值计算，并将支持K-12学生的外展活动。该奖项反映了NSF的法定任务，并认为通过使用该基金会的知识分子和更广泛的Impact Impact Impact Implaster审查Criteria，并被认为是值得通过评估的支持。