权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Computational Complexity Lower Bounds: Time, Space and Communication

AF：小：计算复杂度下限：时间、空间和通信

基本信息

批准号：
2007462
负责人：
Ran Raz
金额：
$ 45万
依托单位：
Princeton University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007462&HistoricalAwards=false
关键词：
AF Small Computational Complexity Lower

项目摘要

While computers have revolutionized our world, the resourcesrequired to perform computational tasks are poorly understood.Developing a mathematical theory of computation is crucial in ourinformation age, where computers are involved in essentially everypart of our life. Computational complexity, the study of the amountof resources needed to perform computational tasks, is essentialfor understanding the power of computation and for the developmentof a theory of computation. It is also essential in designingefficient communication protocols and secure cryptographic protocols,and in understanding human and machine learning. Proving lowerbounds for the resources required by different computationalmodels, and for different computational tasks, is among the mostexciting, most challenging and most important topics in theoreticalcomputer science. The project will study computational complexitylower bounds, focusing on two research directions: Lower boundsrelated to learning; and, studying the relative power of quantumand classical computational models.In more details, we will focus on the following directions. (1)Memory-Samples lower bounds for learning: memory/samples lowerbounds for online learning algorithms is a very exciting researchdirection that has been studied in a line of recent work. Forexample, it was proved that any algorithm for learning paritiesrequires either a memory of quadratic size or an exponential numberof samples. The project will further study memory/samples lowerbounds for learning and their relations to other topics incomputational complexity. (2) The relative power of quantum andclassical computational models: The project will study gaps betweenquantum and classical complexity in various models. In particular, itwill investigate separations between quantum and classical communication complexity,as well as the relative power of quantum and classical algorithmsin the context of memory/samples trade-offs for learning. (3)Circuit complexity lower bounds related to learning: The amazingsuccess of machine learning, and in particular deep learning,motivates a study of closely related computational models. Theproject will study linear-threshold circuits and other models ofcircuits that are related to learning.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）记忆样本学习下界：在线学习算法的记忆/样本下界是一个非常令人兴奋的研究方向，最近的一系列工作都在研究。例如，证明了学习奇偶校验的任何算法需要二次大小的记忆或指数数量的样本。该项目将进一步研究学习的内存/样本下限及其与计算复杂性中其他主题的关系。(2)量子和经典计算模型的相对力量：该项目将研究各种模型中量子和经典复杂性之间的差距。特别是，它将调查量子和经典通信复杂性之间的分离，以及量子和经典算法在学习的内存/样本权衡的背景下的相对功率。（3）与学习相关的电路复杂度下限：机器学习的惊人成功，特别是深度学习，激发了对密切相关的计算模型的研究。该项目将研究线性阈值电路和其他与学习相关的电路模型。该奖项反映了NSF的法定使命，并被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Parallel Repetition Theorem for the GHZ Game

DOI：
发表时间：
2020-08
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
0
作者：
Justin Holmgren;R. Raz
通讯作者：
Justin Holmgren;R. Raz

Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs

所有具有二进制输入的 3 人游戏并行重复的多项式界限

DOI：
发表时间：
2022
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Girish, Uma;Mittal, Kunal;Raz, Ran;Zhan, Wei
通讯作者：
Zhan, Wei

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

使用经典量子混合内存进行学习的内存样本下限

DOI：
10.1145/3564246.3585129
发表时间：
2023
期刊：
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
影响因子：
0
作者：
Liu, Qipeng;Raz, Ran;Zhan, Wei
通讯作者：
Zhan, Wei

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

二次图流算法的近二次下界

DOI：
10.1109/focs46700.2020.00040
发表时间：
2020
期刊：
2020
影响因子：
0
作者：
Assadi, Sepehr;Raz, Ran
通讯作者：
Raz, Ran

Is Untrusted Randomness Helpful?

不可信的随机性有帮助吗？

DOI：
发表时间：
2023
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Girish, Uma;Raz, Ran;Zhan, Wei
通讯作者：
Zhan, Wei

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

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

作者：
{{ item.author }}

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

作者：
{{ item.author }}

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

作者：
{{ item.author }}

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

作者：
{{ item.author }}

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

Ran Raz其他文献

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

DOI：
10.1007/s00037-009-0278-0
发表时间：
2009-11-06
期刊：
COMPUTATIONAL COMPLEXITY
影响因子：
1.000
作者：
Dana Moshkovitz;Ran Raz
通讯作者：
Ran Raz

On the “log rank”-conjecture in communication complexity

论通信复杂性中的“对数秩”猜想

DOI：
10.1007/bf01192528
发表时间：
1995
期刊：
Combinatorica
影响因子：
1.1
作者：
Ran Raz;B. Spieker
通讯作者：
B. Spieker

Resolution lower bounds for the weak pigeon hole principle

DOI：
10.1109/ccc.2002.1004322
发表时间：
2002-05
期刊：
Proceedings 17th IEEE Annual Conference on Computational Complexity
影响因子：
0
作者：
Ran Raz
通讯作者：
Ran Raz

Exponential Separation of Information and Communication for Boolean Functions

布尔函数的信息和通信的指数分离

DOI：
10.1145/2746539.2746572
发表时间：
2015
期刊：
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
影响因子：
0
作者：
Anat Ganor;Gillat Kol;Ran Raz
通讯作者：
Ran Raz