AF: Small: Hardness of Approximation: Classical and New

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

基本信息

  • 批准号:
    2130816
  • 负责人:
  • 金额:
    $ 35万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-10-01 至 2024-09-30
  • 项目状态:
    已结题

项目摘要

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.
计算理论(Theory of Computation,ToC)研究计算的基本性质,其根源可以追溯到由哥德尔、丘奇和图灵开创的逻辑和可计算性理论。在现代形式中,ToC有两个互补的方面:设计有效的算法来解决计算问题(理解计算的能力),并显示可能实现的效率的限制(理解计算的限制)。后一个方面称为计算复杂性;它旨在证明某些计算问题无法有效解决。虽然计算复杂性听起来像是悲观主义的承载者,但它确实导致了对计算本质的深刻见解,有时计算困难的问题实际上是有用和必要的(例如,构建加密系统)。计算复杂性的一个中心现象是“NP完全性”,研究人员强烈认为,一类称为“NP完全问题”的计算问题没有有效的算法。一个著名的例子是旅行推销员(TSP)问题,其中输入是一组城市和它们之间的所有成对距离,目标是计算访问所有城市并遍历最小总距离的旅行。事实证明,在实践中出现的许多问题都是NP完全的,因为这些问题确实需要在实践中解决,一个自然的方法是寻求计算近似解的有效算法。对近似的研究引起了一种被称为“近似困难”的现象,即许多这样的问题甚至很难近似。本项目旨在加深对逼近困难和相关数学工具的理解。该项目主题形成了算法和复杂性之间的桥梁,也是计算机科学和数学之间的桥梁,特别是组合学,分析和几何。该项目的研究方面将与教育(本科和研究生两级的教学课程和指导学生)和传播活动(研究讲座,撰写调查报告等)相结合。从20世纪90年代初的基本概率可检验证明(PCP)定理开始,近似的硬度有许多有影响力的结果,包括最近的2对2博弈猜想的证明(由研究者和合作者)。该项目的重点是进一步的问题,近似和分析工具的硬度需要回答这些问题。它考虑了经典的设置多项式时间的可逼近性,以及新的设置固定参数的易处理性和细粒度的复杂性。在经典环境中,该项目的主要重点是描述约束满足问题(CSP)在可满足实例上的近似性,并开发分析工具以实现这种特性。为了详细说明,人们注意到,给定“三可满足性”(3SAT)问题的可满足实例,已知如何有效地找到满足其子句的7/8分数的赋值,而且,要做得更好是NP完全的。该项目将专注于证明每个CSP的类似结果。近年来,研究人员在固定参数易处理性和细粒度复杂性的邻近领域取得了进展。在固定参数易处理性中,人们通常考虑已知为NP完全的问题(例如顶点覆盖),并寻求其运行时间是输入(例如图)大小的(固定)多项式和指定参数(例如顶点覆盖大小)的任意函数的算法。在细粒度复杂性中,人们考虑一个已知具有多项式时间算法的问题,并且关注的是多项式的精确指数。在这两种情况下,考虑近似值和精确解是很自然的。在固定参数设置下,本项目将着重于证明经典PCP定理的类比。在细粒度设置中,重点将放在一些几何问题上,如最近对,远距离对,直径和编辑距离。该项目还将研究分析问题,这些问题不一定与近似的难度有关,但属于研究者的长期目标。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
On Approximability of Satisfiable k-CSPs: I
关于可满足 k-CSP 的近似性:I
Almost polynomial factor inapproximability for parameterized k-clique
An Invariance Principle for the Multi-slice, with Applications
多切片不变性原理及其应用
  • DOI:
    10.1109/focs52979.2021.00030
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Braverman, Mark;Khot, Subhash;Lifshitz, Noam;Minzer, Dor
  • 通讯作者:
    Minzer, Dor
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Subhash Khot其他文献

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
在 2 色和几乎 2 色超图中寻找独立集的难度
Guest column: inapproximability results via Long Code based PCPs
来宾专栏:通过基于长代码的 PCP 得出的​​不可近似性结果
  • DOI:
    10.1145/1067309.1067318
  • 发表时间:
    2005
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Subhash Khot
  • 通讯作者:
    Subhash Khot
Towards a proof of the 2-to-1 games conjecture?
证明2对1游戏猜想?
Inapproximability Results for Computational Problems on Lattices
  • DOI:
    10.1007/978-3-642-02295-1_14
  • 发表时间:
    2010
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Subhash Khot
  • 通讯作者:
    Subhash Khot
Effective Bounds for Restricted 3-Arithmetic Progressions in Fpn
Fpn 中受限 3 算术级数的有效界限

Subhash Khot的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Subhash Khot', 18)}}的其他基金

AF: Small: Analysis, Geometry, and Hardness of Approximation
AF:小:分析、几何和近似硬度
  • 批准号:
    1813438
  • 财政年份:
    2018
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Challenges in Hardness of Approximation
AF:小:近似难度的挑战
  • 批准号:
    1422159
  • 财政年份:
    2014
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
2010 Waterman Award
2010年沃特曼奖
  • 批准号:
    1061938
  • 财政年份:
    2010
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs
职业:不可近似性和概率可检查证明的新方向
  • 批准号:
    0833228
  • 财政年份:
    2008
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant
Collaborative Research: Understanding, Coping with, and Benefiting From, Intractability
合作研究:理解、应对棘手问题并从中受益
  • 批准号:
    0832795
  • 财政年份:
    2008
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant
CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs
职业:不可近似性和概率可检查证明的新方向
  • 批准号:
    0643626
  • 财政年份:
    2007
  • 资助金额:
    $ 35万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

AF: Small: Hardness of Approximation Meets Parameterized Complexity
AF:小:近似难度满足参数化复杂性
  • 批准号:
    2313372
  • 财政年份:
    2023
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: The Unique Games Conjecture and Related Problems in Hardness of Approximation
AF:小:独特的博弈猜想及近似难度中的相关问题
  • 批准号:
    2200956
  • 财政年份:
    2022
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: CISE-ANR: CNS Core: Small: Cryptographic Hardness of Module Lattices
合作研究:CISE-ANR:CNS 核心:小型:模块格的密码硬度
  • 批准号:
    2122229
  • 财政年份:
    2021
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
Collaborative Research: CISE-ANR: CNS Core: Small: Cryptographic Hardness of Module Lattices
合作研究:CISE-ANR:CNS 核心:小型:模块格的密码硬度
  • 批准号:
    2122230
  • 财政年份:
    2021
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Geometric Inequalities, Clustering Hardness, and Social Choice
AF:小:几何不等式、聚类难度和社会选择
  • 批准号:
    1911216
  • 财政年份:
    2019
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Analysis, Geometry, and Hardness of Approximation
AF:小:分析、几何和近似硬度
  • 批准号:
    1813438
  • 财政年份:
    2018
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Boolean Functions: Inequalities, Structure, Algorithms & Hardness
AF:小:布尔函数:不等式、结构、算法
  • 批准号:
    1665252
  • 财政年份:
    2016
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Approximate optimization: Algorithms, Hardness, and Integrality Gaps
AF:小:近似优化:算法、硬度和完整性差距
  • 批准号:
    1526092
  • 财政年份:
    2015
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Challenges in Hardness of Approximation
AF:小:近似难度的挑战
  • 批准号:
    1422159
  • 财政年份:
    2014
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
AF: Small: Boolean Functions: Inequalities, Structure, Algorithms & Hardness
AF:小:布尔函数:不等式、结构、算法
  • 批准号:
    1320105
  • 财政年份:
    2013
  • 资助金额:
    $ 35万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了