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 不同，则有许多重要的计算问题无法有效解决。对于应用程序来说更重要的是（因为在实践中通常不需要精确的解决方案），甚至近似解决其中一些问题在计算上也很困难。研究这个主题的领域被称为“近似硬度”，在过去二十年中取得了突飞猛进的发展。该领域的开创性成就之一是在几何和概率中的计算复杂性与等周型问题之间建立了深刻的联系。平面上的等周长问题——人们已经知道并研究了两千年以上——询问给定区域的哪种形状具有最小周长（答案：圆形）。如果更好地理解这个问题的某些概率、高维变体，它将解决近似硬度方面的几个开放问题。更好地理解高效近似计算的局限性将反过来为现实世界的计算问题带来更好的算法。该项目旨在加强近似硬度、几何和概率之间的联系。通过解决几何和概率中的新的最优划分问题，研究人员将开发算法并证明新的算法硬度结果。这些划分问题的困难之一是存在组合的许多鞍点或局部极小值，但研究者最近（与 E. Milman）对高斯双泡猜想的解决方案包括一种规避这一困难的新方法。这些最优划分问题的算法结果包括（i）改进测试和学习几何概念类的界限； (ii) 改进的非交互式相关蒸馏算法（密码学中的一个问题，应用于随机信标和信息协调）； (iii) 经典通信和量子通信复杂性之间的更强分离。该奖项将允许研究生和本科生参与相关研究项目，资助数值计算开源软件的开发，并支持 K-12 学生的外展活动。该奖项反映了 NSF 的法定使命，并已被通过使用基金会的智力优点和更广泛的影响审查标准进行评估，认为值得支持。