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

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

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.