AF: Small: Hardness of Approximation: Classical and New

AF：小：近似难度：经典和新

• 批准号: 2130816
• 负责人: Subhash Khot
• 金额: $ 35万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2130816&HistoricalAwards=false
• 关键词: AF; Small; Hardness; Approximation; Classical

Theory of Computation (ToC) studies the fundamental nature of computation with its roots going back to logic and computability theory pioneered by Godel, Church, and Turing. In its modern form, ToC has two complementary aspects: to design efficient algorithms to solve computational problems (understanding the power of computation) and to show limitations, if any, on the efficiency that may be achieved (understanding the limits of computation). The latter aspect is called computational complexity; it aims at demonstrating that certain computational problems cannot be solved efficiently. While computational complexity sounds like a bearer of pessimism, it does lead to deep insights into nature of computation and sometimes having computationally hard problems is actually useful and necessary (e.g., to build cryptographic systems). A central phenomenon in computational complexity is "NP-completeness", whereby researchers strongly believe that a class of computational problems called the "NP-complete problems" have no efficient algorithms. A well-known example is the Traveling Salesperson (TSP) problem, where the input is a set of cities and all pairwise distances between them and the goal is to compute a tour that visits all the cities and traverses the minimum total distance. It turns out that a host of problems arising in practice are NP-complete and since these do need to be solved in practice, a natural approach is to seek efficient algorithms that compute approximate solutions. The study of approximation gives rise to a further phenomenon known as "hardness of approximation", namely that many such problems turn out to be hard even to approximate. This project aims to deepen the understanding of hardness of approximation and related mathematical tools. The project topic forms a bridge between algorithms and complexity, and also as a bridge between computer science and mathematics, especially combinatorics, analysis, and geometry. The research aspect of the project will be integrated with education (teaching courses and advising students at both undergraduate and graduate levels) and dissemination activities (research talks, writing surveys, etc.). Starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem in the early 1990s, there are numerous influential results in Hardness of Approximation, including the recent proof of the 2-to-2 Games Conjecture (by the investigator and collaborators). The project focuses on further questions in hardness of approximation and analytic tools needed to answer these questions. It considers the classical setting of polynomial-time approximability as well as the new settings of fixed parameter tractability and fine-grained complexity. In the classical setting, the main focus of the project is to characterize approximability of Constraint Satisfaction Problems (CSPs) on satisfiable instances and developing analytic tools towards such a characterization. To elaborate, one notes that given a satisfiable instance of a "three-satisfiability" (3SAT) problem, it is known how to efficiently find an assignment that satisfies 7/8 fraction of its clauses and moreover, that it is NP-complete to do better. The project will focus on proving analogous results for every CSP. In recent years, researchers have been making progress in neighboring areas of fixed parameter tractability and fine-grained complexity. In fixed parameter tractability, one typically considers a problem that is known to be NP-complete (e.g. Vertex Cover) and seeks an algorithm whose running time is a (fixed) polynomial in the size of the input (e.g. the graph) and an arbitrary function of a designated parameter (e.g. the vertex cover size). In fine-grained complexity, one considers a problem that is known to have a polynomial-time algorithm, and the concern is the precise exponent of the polynomial. In both settings, it is natural to consider approximations as well as exact solutions. In the fixed parameter setting, the project will focus on proving the analogue of the classical PCP Theorem. In the fine-grained setting, the focus will be on some geometric problems such as Closest Pair, Farthest Pair, Diameter, and Edit Distance. The project will also study analytic questions that are not necessarily related to hardness of approximation, but are among investigator's long-term goals.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.

计算理论（TOC）研究了计算的基本性质，其根源可以追溯到Godel，Church和Turing开创的逻辑和计算理论。 TOC以其现代形式有两个互补的方面：设计有效的算法来解决计算问题（了解计算的功能），并显示出可能达到的效率（了解计算的限制）的局限性（如果有的话）。后一个方面称为计算复杂性。它旨在证明无法有效解决某些计算问题。虽然计算复杂性听起来像是悲观主义的承载者，但它确实可以深入了解计算本质，有时在计算上存在硬性问题实际上是有用和必要的（例如，构建加密系统）。计算复杂性中的一种核心现象是“ NP完整性”，研究人员强烈认为，一类称为“ NP-Complete问题”的计算问题没有有效的算法。一个众所周知的例子是旅行销售人员（TSP）问题，其中输入是一组城市，它们之间的所有成对距离是计算访问所有城市并穿越最小总距离的游览。事实证明，实践中出现的许多问题是NP完整的，并且由于实际上需要解决这些问题，因此一种自然的方法是寻求计算近似解决方案的有效算法。近似的研究产生了一种被称为“近似硬度”的现象，即，许多这样的问题甚至很难近似。该项目旨在加深对近似和相关数学工具硬度的理解。该项目主题在算法和复杂性之间形成了桥梁，也形成了计算机科学与数学之间的桥梁，尤其是组合学，分析和几何形状。该项目的研究方面将与教育（教学课程和本科和研究生级别的学生提供建议）和传播活动（研究谈判，写作调查等）。从1990年代初期的基础概率可检查证明（PCP）定理开始，近似硬度有许多有影响力的结果，包括最近2-2游戏的证明（研究人员和合作者）。该项目着重于回答这些问题所需的近似和分析工具硬度的进一步问题。它考虑了多项式时间近似性的经典设置以及固定参数障碍性和细粒复杂性的新设置。在经典环境中，该项目的主要重点是表征约束满意度问题（CSP）在可满足实例上的近似性，并开发了用于这种表征的分析工具。为了详细说明，有一个指出的是，给出了一个“三个可满足性”（3SAT）问题的令人满意的实例，众所周知，如何有效地找到满足其子句的7/8分的作业，此外，做得更好是NP完整的。该项目将集中于证明每个CSP的类似结果。近年来，研究人员一直在固定参数障碍性和细粒度复杂性的邻近地区取得进展。在固定参数障碍性中，通常会考虑一个已知已知为NP完整的问题（例如顶点封面），并寻求一种算法，其运行时间为输入大小（例如图形）（例如图形）和指定参数的任意功能的算法（例如，指定参数（例如，VERTEX封面尺寸）。在细粒度的复杂性中，人们考虑了一个已知具有多项式时间算法的问题，而关注的问题是多项式的确切指数。在这两种情况下，自然要考虑近似值以及精确的解决方案。在固定参数设置中，该项目将专注于证明经典PCP定理的类似物。在细粒度的环境中，焦点将放在一些几何问题上，例如最接近的对，最远的对，直径和编辑距离。该项目还将研究不一定与近似硬度有关的分析问题，而是研究者的长期目标之一。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响审查标准，认为值得通过评估来支持。

项目成果

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
• 作者: Bhangale, Amey;Khot, Subhash;Minzer, Dor
• 通讯作者: Minzer, Dor

Almost polynomial factor inapproximability for parameterized k-clique

• DOI: 10.4230/lipics.ccc.2022.6
• 发表时间: 2021-12
• 期刊: Proceedings of the 37th Computational Complexity Conference
• 作者: C. Karthik;Subhash Khot

An Invariance Principle for the Multi-slice, with Applications

多切片不变性原理及其应用

• DOI: 10.1109/focs52979.2021.00030
• 发表时间: 2022
• 期刊: FOCS 2021 conference
• 作者: Braverman, Mark;Khot, Subhash;Lifshitz, Noam;Minzer, Dor
• 通讯作者: Minzer, Dor