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其他文献

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