AF: SMALL: On the Complexity of Satisfiable CSPs
AF:小:关于可满足的 CSP 的复杂性
基本信息
- 批准号:2227876
- 负责人:
- 金额:$ 60万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-01-01 至 2025-12-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
Complexity Theory is the study of resources (time, memory, number of processors) needed to execute computational tasks, whose main goal is to classify computational problems as feasible (i.e., problems that can be solved efficiently) or as infeasible (i.e., problems that cannot be solved efficiently). Probabilistically Checkable Proofs is a sub-area of Complexity Theory that extends this study to the realm of approximation problems and shows that for many computational tasks, even coming up with an approximate solution may be computationally infeasible. Nowadays, results from this area are also used in real-life applications in non-centralized systems such as blockchains and cryptocurrencies. The goal of this project is to further develop the theory of Probabilistically Checkable Proofs and address new, as well as long-standing, challenges in the area. The project combines various branches of computer science and mathematics and may impact other scientific fields. The project's activities include course development, mentoring, and workshop organization. In more detail, this project focuses on studying satisfiable constraint satisfaction problems. The class of constraint satisfaction problems (CSPs in short) is one of the most fundamental classes of problems in complexity theory. An instance of a problem consists of a collection of undetermined variables, as well as a collection of constraints imposed on them; the goal is to find an assignment to the variables that satisfies as many of the constraints as possible. What is the best, most efficient approximation algorithm to this problem, provided that a solution that satisfies all of the constraints exists? This project is driven by this meta question, aiming to create new tools as well as form new connections with other mathematical areas.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.
复杂性理论是对执行计算任务所需的资源(时间,内存,处理器数量)的研究,其主要目标是将计算问题分类为可行的(即,可以有效解决的问题)或不可行的问题(即,无法有效解决的问题)。概率可检验证明是复杂性理论的一个子领域,它将这项研究扩展到近似问题领域,并表明对于许多计算任务,即使提出近似解也可能在计算上不可行。如今,这一领域的成果也被用于非中心化系统的实际应用中,如区块链和加密货币。该项目的目标是进一步发展概率可检验证明的理论,并解决该领域新的和长期存在的挑战。该项目结合了计算机科学和数学的各个分支,并可能影响其他科学领域。该项目的活动包括课程开发、辅导和讲习班组织。更详细地说,这个项目的重点是研究可满足的约束满足问题。约束满足问题是复杂性理论中最基本的一类问题。一个问题的实例由一组未确定的变量和一组约束条件组成;目标是找到一个尽可能满足约束条件的变量赋值。如果存在满足所有约束条件的解,那么这个问题的最佳、最有效的近似算法是什么?这个项目是由这个Meta问题驱动的,旨在创造新的工具,以及与其他数学领域形成新的联系。这个奖项反映了NSF的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
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 }}
Dor Minzer其他文献
Small Set Expansion in The Johnson Graph
约翰逊图中的小集展开
- DOI:
- 发表时间:
2018 - 期刊:
- 影响因子:0
- 作者:
Subhash Khot;Dor Minzer;Dana Moshkovitz;S. Safra - 通讯作者:
S. Safra
On Approximability of Satisfiable k-CSPs: IV
关于可满足 k-CSP 的近似性:IV
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Amey Bhangale;Subhash Khot;Dor Minzer - 通讯作者:
Dor Minzer
Noise Sensitivity on the p -Biased Hypercube
p 偏超立方体上的噪声灵敏度
- DOI:
10.1109/focs.2019.00075 - 发表时间:
2019 - 期刊:
- 影响因子:0
- 作者:
Noam Lifshitz;Dor Minzer - 通讯作者:
Dor Minzer
Towards a proof of the 2-to-1 games conjecture?
证明2对1游戏猜想?
- DOI:
10.1145/3188745.3188804 - 发表时间:
2018 - 期刊:
- 影响因子:0
- 作者:
Irit Dinur;Subhash Khot;Guy Kindler;Dor Minzer;S. Safra - 通讯作者:
S. Safra
On the largest product-free subsets of the alternating groups
- DOI:
10.1007/s00222-024-01273-1 - 发表时间:
2024-05-29 - 期刊:
- 影响因子:3.600
- 作者:
Peter Keevash;Noam Lifshitz;Dor Minzer - 通讯作者:
Dor Minzer
Dor Minzer的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Dor Minzer', 18)}}的其他基金
CAREER: New Challenges in Analysis of Boolean Functions
职业:布尔函数分析的新挑战
- 批准号:
2239160 - 财政年份:2023
- 资助金额:
$ 60万 - 项目类别:
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 RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: Computational Complexity and Algebraic Combinatorics
合作研究:AF:小:计算复杂性和代数组合
- 批准号:
2302174 - 财政年份:2023
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: Hardness of Approximation Meets Parameterized Complexity
AF:小:近似难度满足参数化复杂性
- 批准号:
2313372 - 财政年份:2023
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Computational Complexity and Algebraic Combinatorics
合作研究:AF:小:计算复杂性和代数组合
- 批准号:
2302173 - 财政年份:2023
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: The complexity of matrix multiplication
AF:小:矩阵乘法的复杂度
- 批准号:
2203618 - 财政年份:2022
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: Streaming Complexity of Constraint Satisfaction Problems
AF:小:约束满足问题的流复杂性
- 批准号:
2152413 - 财政年份:2022
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: Polynomials, Communication, and Query Complexity
AF:小:多项式、通信和查询复杂性
- 批准号:
2220232 - 财政年份:2022
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Weak Derandomizations in Time and Space Complexity
合作研究:AF:小:时间和空间复杂性的弱去随机化
- 批准号:
2130608 - 财政年份:2021
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: Lower bounds on concrete complexity
NSF-BSF:AF:小:具体复杂性的下限
- 批准号:
2131899 - 财政年份:2021
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: New Approaches to Complexity Theory Lower Bounds
AF:小:复杂性理论下界的新方法
- 批准号:
2114116 - 财政年份:2021
- 资助金额:
$ 60万 - 项目类别:
Standard Grant
AF: Small: Lower Bounds in Complexity Theory Via Algorithms
AF:小:通过算法实现复杂性理论的下界
- 批准号:
2127597 - 财政年份:2021
- 资助金额:
$ 60万 - 项目类别:
Standard Grant