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

AF: Small: Analysis, Geometry, and Hardness of Approximation

AF：小：分析、几何和近似硬度

基本信息

批准号：
1813438
负责人：
Subhash Khot
金额：
$ 50万
依托单位：
New York University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813438&HistoricalAwards=false
关键词：
AF Small Analysis Geometry Hardness

项目摘要

Algorithms are systematic procedures to solve computational problems. There are a class of problems called "NP-hard" problems which are believed to be computationally infeasible or "hard", and without any efficient algorithms. A well-known representative problem in this class is the Travelling Salesperson (TSP) problem: given a large number of cities and pairwise distances among them, what is the minimum length tour that visits all the cities? NP-hard problems, though computationally hard, do arise in practice and do need to be "solved" somehow. A natural approach is to design efficient algorithms that compute approximate solutions along with a guarantee on the quality of approximation. In the case of TSP, there is an efficient algorithm that computes a tour that is guaranteed to be at most 1% longer than the minimum length tour (which might be good enough in practice). A huge amount of research has been devoted to designing good approximation algorithms for numerous NP-hard problems. However, it is also of interest to investigate whether there are limitations on the quality of approximation that can be achieved by an efficient algorithm. Indeed, it turns out that for several NP-hard problems, computing an approximation better than a specific threshold is as hard as computing the exact solution (and hence infeasible). These latter kind of results, called "hardness of approximation" results, are the focus of this project. The project aims at studying analytic and geometric questions that are motivated by their applications to theoretical computer science (TCS) and primarily to hardness of approximation. The research goals of the proposal will be integrated with teaching, mentoring, and dissemination activities.Hardness of approximation has been a highly influential topic of research starting with the Probabilistically Checkable Proofs (PCP) Theorem in early 1990s. While there have been major successes towards characterizing precise approximation thresholds for basic NP-hard problems, this quest remains largely open. The investigator for this project proposed the Unique Games Conjecture (UGC) in 2002 to make further progress, which turned out to be quite successful, and led to many novel research directions. This project focuses on (1) the analytic and geometric questions that arise from the investigator's recent work towards proving the UGC; (2) understanding the phenomenon of approximation resistance of predicates (which would certainly lead to challenging analytic questions and would likely be related to the recently resolved Dichotomy Conjecture); (3) analytic questions that are not necessarily related to hardness of approximation, but are among long-term goals in this area at the interface of analysis, geometry, and hardness of approximation.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.

算法是解决计算问题的系统程序。有一类问题被称为“NP-Hard”问题，它们被认为在计算上是不可行的或“难的”，并且没有任何有效的算法。这一类中一个著名的代表性问题是旅行商(TSP)问题：假设有大量的城市和城市之间的两两距离，那么访问所有城市的最短行程是多少？NP-Hard问题虽然在计算上很难，但在实践中确实会出现，确实需要以某种方式“解决”。一种自然的方法是设计高效的算法来计算近似解，同时保证近似的质量。在TSP的情况下，有一个高效的算法来计算保证最多比最小长度巡视长1%的巡视(这在实践中可能已经足够好了)。大量的研究致力于为大量的NP-Hard问题设计良好的近似算法。然而，调查高效算法所能实现的近似质量是否存在限制也是很有意义的。事实上，事实证明，对于几个NP-Hard问题，计算比特定阈值更好的近似值与计算精确解一样困难(因此是不可行的)。后一类结果，称为“逼近硬度”结果，是本项目的重点。该项目旨在研究解析和几何问题，这些问题的动机是它们在理论计算机科学(TCS)中的应用，主要是近似的难度。该提案的研究目标将与教学、指导和传播活动相结合。从20世纪90年代初的概率可检验证明(PCP)定理开始，逼近的坚固性一直是一个非常有影响力的研究主题。虽然在刻画基本NP困难问题的精确近似阈值方面已经取得了重大成功，但这一探索在很大程度上仍然是开放的。2002年，该项目的研究者提出了独特的游戏猜想(UGC)，并取得了进一步的进展，取得了相当成功的结果，并导致了许多新的研究方向。这个项目的重点是(1)研究人员最近在证明UGC的工作中产生的分析和几何问题；(2)理解谓词的近似阻力现象(这肯定会导致挑战性的分析问题，很可能与最近解决的二分法猜想有关)；(3)分析问题，这些问题不一定与近似的难易程度有关，但在分析、几何和近似的难易程度上是这一领域的长期目标之一。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On Approximability of Satisfiable k-CSPs: I

关于可满足 k-CSP 的近似性：I

DOI：
10.1145/3519935.3520028
发表时间：
2022
期刊：
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Bhangale, Amey;Khot, Subhash;Minzer, Dor
通讯作者：
Minzer, Dor

Almost polynomial factor inapproximability for parameterized k-clique