AF: Small: Intermediate models between communication complexity and query complexity
AF: Small: Intermediate models between communication complexity and query complexity
批准号:
2006443
负责人:
Shachar Lovett
金额:
$30.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2020
资助国家:
美国
项目状态:
已结题
起止时间:
2020-08-01 至 2024-06-30
中文摘要
40多年来,通信复杂性一直是计算机科学的一个充满活力的子领域。它的核心是研究分布式问题,其中每个参与者接收问题的一部分,参与者需要合作并共享信息以找到解决方案。该领域的许多著名成果都涉及计算出解决与计算机科学的许多其他领域相关的某些具体重要问题需要多少沟通。另一方面,只有很少的技术可以理解一般的沟通问题。这与更简单的计算模型的情况相反,特别是查询复杂性。可以肯定地说,今天对一般问题的查询复杂性已经有了完整的定性的,并且在很大程度上是定量的理解。这个项目的重点是中间模型,它在通信复杂性和查询复杂性之间进行插值。我们的目标是在这些受限制的模型中理解通信复杂性的基本开放问题,以便开发新的工具和技术,然后可以扩展到一般的通信复杂性。该奖项旨在解决的通信复杂性的主要问题是:*哪些功能允许有效的通信协议?*这些函数是否具有代数、解析或组合性质?*高效通信协议的结构是什么?*在交流复杂性中随机性的力量是什么?我们的计划是将这些问题限制在一类特殊的问题中,称为提升函数。这些包含了许多经过充分研究的函数的自然示例,并且还产生了自然的中间模型,例如奇偶决策树和and决策树。这些模型比标准查询复杂性更强大,比一般通信复杂性更结构化,因此是开发新技术的理想测试平台。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
英文摘要
Communication complexity has been a vibrant sub-field of computer science for more than 40 years. At its core, it studies distributed problems, where each player receives a part of a problem, and the players need to cooperate and share information in order to find a solution. Many of the celebrated results in the field involve figuring out exactly how much communication is needed to solve certain concrete important problems with relevance in many other domains in computer science. On the other hand, there are only few techniques to understand general communication problems.This is in contrast with the situation in simpler computational models, notably query complexity. It is safe to say that today there is a complete qualitative, and to a large extent quantitative, understanding of the query complexity of generic problems. The focus of this project is on intermediate models, which interpolate between communication complexity and query complexity. The goal is to to understand fundamental open problems in communication complexity in these restricted models, in order to develop new tools and techniques that then may be extended to general communication complexity.The main questions in communication complexity that this award aims to tackle are:* Which functions admit efficient communication protocols?* Are there algebraic, analytic or combinatorial properties that characterize such functions?* What is the structure of efficient communication protocols?* What is the power of randomness in communication complexity?The plan is to consider these questions restricted to a special class of problems, called lifted functions. These contain many natural examples of well-studied functions, and also give rise to natural intermediate models, such as parity decision trees and AND decision trees. These models are more powerful than standard query complexity, and more structured than general communication complexity, and as such are an ideal test bed to develop new techniques.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.
期刊论文(1)
专著(0)
科研奖励(0)
会议论文
Log-rank and lifting for AND-functions
AND 函数的对数排序和提升
DOI:
10.1145/3406325.3450999
发表时间:
2021
期刊:
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子:
--
作者:
[Knop, Alexander, Lovett, Shachar, McGuire, Sam, Yuan, Weiqiang]
通讯作者:
Yuan, Weiqiang
The Sunflower Conjecture, Disjunctive Normal Forms, and Beyond
-
批准号:1953928
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2020
-
负责人:Shachar Lovett
-
依托单位:
AF: Small: Rare Events - New Probabilistic and Algorithmic Techniques
-
批准号:1614023
-
项目类别:Standard Grant
-
资助金额:$45.0万
-
财政年份:2016
-
负责人:Shachar Lovett
-
依托单位:
CAREER: Algebraic and Combinatorial Structures In Complexity Theory
-
批准号:1350481
-
项目类别:Continuing Grant
-
资助金额:$50.0万
-
财政年份:2014
-
负责人:Shachar Lovett
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: