AF: Small: Lower Bounds for Computational Models, and Relations to Other Topics in Computational Complexity
AF:小:计算模型的下界以及与计算复杂性中其他主题的关系
基本信息
- 批准号:1714779
- 负责人:
- 金额:$ 45万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2017
- 资助国家:美国
- 起止时间:2017-09-01 至 2021-08-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Computational complexity theory is a mathematical field that studies the limits of computers and the resources needed to perform computational tasks. A mathematical theory of computation is crucial in our information age, where computers are involved in essentially every part of our life. Computational complexity is also essential in designing efficient communication protocols, secure cryptographic protocols and in understanding human and machine learning. Studying the limits of computational models is among the most exciting, most challenging, and most important topics in theoretical computer science and is essential for understanding the power of computation and for the development of a theory of computation.The project will study lower bounds for the resources required by different computational models, as well as related topics in computational complexity. The project will focus on three main research directions:Time-Space lower bounds for learning: In a sequence of recent works, the PI and his coauthors proved that some of the most extensively studied learning problems require either a super-linear memory size or a super-polynomial number of samples. The project will further study memory/samples lower bounds for learning and their relations to other topics in complexity theory. Lower bounds for learning under memory constraints demonstrate the importance of memory in learning and cognitive processes. They may be relevant to understanding human learning and may have impact on machine learning, artificial intelligence and optimization. They also have applications in cryptography.Lower bounds for arithmetic circuits: The project will study lower bounds for arithmetic circuits and formulas, as well as for subclasses of arithmetic circuits and formulas. Lower bounds for arithmetic circuits may have a broader impact within theoretical computer science, because of the centrality of polynomials in theoretical computer science.Lower bounds for communication complexity: In a sequence of recent works, the PI and his coauthors proved the first gaps between information complexity and communication complexity. These results show that compression of interactive communication protocols to their information content is not possible, and hence show that interactive analogs to Shannon's source coding theorem and Huffman coding are not possible. Separation results of communication complexity and information complexity may be relevant to electrical engineering and in particular to the design of efficient communication protocols. The project will further study these topics, and more generally, lower bounds for communication complexity and their relations to other topics in computational complexity.
计算复杂性理论是一个研究计算机局限性和执行计算任务所需资源的数学领域。计算的数学理论在我们的信息时代至关重要,计算机基本上涉及我们生活的每个部分。计算复杂性对于设计高效的通信协议、安全的加密协议以及理解人类和机器学习也至关重要。研究计算模型的局限性是理论计算机科学中最令人兴奋、最具挑战性和最重要的主题之一,对于理解计算的力量和计算理论的发展至关重要。该项目将研究不同计算模型所需的资源,以及计算复杂性的相关主题。该项目将重点关注三个主要研究方向:学习的时空下界:在最近的一系列工作中,PI 和他的合著者证明,一些最广泛研究的学习问题需要超线性内存大小或样本的超多项式数。该项目将进一步研究学习的记忆/样本下限及其与复杂性理论中其他主题的关系。记忆限制下的学习下限证明了记忆在学习和认知过程中的重要性。它们可能与理解人类学习相关,并可能对机器学习、人工智能和优化产生影响。它们在密码学中也有应用。算术电路的下界:该项目将研究算术电路和公式以及算术电路和公式的子类的下界。由于多项式在理论计算机科学中的中心地位,算术电路的下界可能在理论计算机科学中产生更广泛的影响。通信复杂性的下界:在最近的一系列工作中,PI 和他的合著者证明了信息之间的第一个差距复杂性和通信复杂性。这些结果表明,将交互式通信协议压缩为其信息内容是不可能的,因此表明香农源编码定理和霍夫曼编码的交互式模拟是不可能的。通信复杂性和信息复杂性的分离结果可能与电气工程相关,特别是与高效通信协议的设计相关。该项目将进一步研究这些主题,更广泛地研究通信复杂性的下限及其与计算复杂性中其他主题的关系。
项目成果
期刊论文数量(16)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Oracle separation of BQP and PH
Oracle BQP 和 PH 分离
- DOI:10.1145/3313276.3316315
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Raz, Ran;Tal, Avishay
- 通讯作者:Tal, Avishay
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
二次图流算法的近二次下界
- DOI:10.1109/focs46700.2020.00040
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Assadi, Sepehr;Raz, Ran
- 通讯作者:Raz, Ran
The Random-Query Model and the Memory-Bounded Coupon Collector
随机查询模型和内存有限的优惠券收集器
- DOI:10.4230/lipics.itcs.2020.20
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Raz, Ran;Zhan, Wei
- 通讯作者:Zhan, Wei
Parallel Repetition for the GHZ Game: A Simpler Proof
GHZ 游戏的并行重复:更简单的证明
- DOI:10.4230/lipics.approx/random.2021.62
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Girish, Uma;Holmgren, Justin;Mittal, Kunal;Raz, Ran;Zhan, Wei
- 通讯作者:Zhan, Wei
Memory-Sample Lower Bounds for Learning Parity with Noise
用于学习与噪声的奇偶校验的内存样本下界
- DOI:10.4230/lipics.approx/random.2021.60
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Garg, Sumegha;Kothari, Pravesh;Liu, Pengda;Raz, Ran
- 通讯作者:Raz, Ran
{{
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 }}
Ran Raz其他文献
Exponential Separation of Information and Communication for Boolean Functions
布尔函数的信息和通信的指数分离
- DOI:
10.1145/2746539.2746572 - 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
Anat Ganor;Gillat Kol;Ran Raz - 通讯作者:
Ran Raz
On the “log rank”-conjecture in communication complexity
论通信复杂性中的“对数秩”猜想
- DOI:
10.1007/bf01192528 - 发表时间:
1995 - 期刊:
- 影响因子: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 - 期刊:
- 影响因子:0
- 作者:
Ran Raz - 通讯作者:
Ran Raz
Resolution lower bounds for the weak pigeonhole principle
弱鸽巢原理的分辨率下限
- DOI:
10.1145/972639.972640 - 发表时间:
2004 - 期刊:
- 影响因子:0
- 作者:
Ran Raz - 通讯作者:
Ran Raz
Ran Raz的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Ran Raz', 18)}}的其他基金
AF: Small: Computational Complexity Lower Bounds: Time, Space and Communication
AF:小:计算复杂度下限:时间、空间和通信
- 批准号:
2007462 - 财政年份:2020
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
相似国自然基金
METTL3通过m6A修饰降低BECN1稳定性抑制自噬导致小细胞肺癌放疗抵抗的机制
- 批准号:82303693
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
Junctophilin-2衍生小肽降低小鼠心律失常机制的研究
- 批准号:82360073
- 批准年份:2023
- 资助金额:32 万元
- 项目类别:地区科学基金项目
MTA3通过促进谷氨酰胺合成酶介导的肿瘤干性降低非小细胞肺癌放射敏感性的机制研究
- 批准号:82303673
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
低频超声-羰氨缩合降低小清蛋白致敏性的分子机制研究
- 批准号:31960457
- 批准年份:2019
- 资助金额:40 万元
- 项目类别:地区科学基金项目
锌离子通过NF-κB信号通路靶向调控小胶质/巨噬细胞降低脊髓损伤神经元焦亡的机制研究
- 批准号:81871556
- 批准年份:2018
- 资助金额:58.0 万元
- 项目类别:面上项目
相似海外基金
NSF-BSF: AF: Small: Lower bounds on concrete complexity
NSF-BSF:AF:小:具体复杂性的下限
- 批准号:
2131899 - 财政年份:2021
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF: Small: Lower Bounds in Complexity Theory Via Algorithms
AF:小:通过算法实现复杂性理论的下界
- 批准号:
2127597 - 财政年份:2021
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF: Small: New Approaches to Complexity Theory Lower Bounds
AF:小:复杂性理论下界的新方法
- 批准号:
2114116 - 财政年份:2021
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF: Small: Computational Complexity Lower Bounds: Time, Space and Communication
AF:小:计算复杂度下限:时间、空间和通信
- 批准号:
2007462 - 财政年份:2020
- 资助金额:
$ 45万 - 项目类别:
Standard Grant
AF:Small: Derandomization and Lower Bounds
AF:Small:去随机化和下界
- 批准号:
1319822 - 财政年份:2013
- 资助金额:
$ 45万 - 项目类别:
Standard Grant