Towards a Unified Theory of Proof and Circuit Complexity

走向证明和电路复杂性的统一理论

基本信息

  • 批准号:
    RGPIN-2021-03036
  • 负责人:
  • 金额:
    $ 3.35万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2021
  • 资助国家:
    加拿大
  • 起止时间:
    2021-01-01 至 2022-12-31
  • 项目状态:
    已结题

项目摘要

Consider the following problem: you are given an extremely large (say, 10,000 digit) number, and are asked to find any number (other than 1 or itself) that divides it. This problem is, apparently, very hard for powerful computers to solve efficiently. Moreover, much of the technology of the modern world crucially relies on the fact that this problem is hard to solve, since its hardness is the foundation of the cryptography that keeps all of our internet communications safe! Such questions about the intrinsic hardness of computational tasks are the study of computational complexity theory, which is my area of research. In complexity theory, we study the amounts of resources --- like running time, memory, or energy --- that computers must consume to perform their computations. In this way, computational complexity is the flip side of the coin to algorithm design, which is concerned with finding the most efficient algorithms for a given task. This research proposal outlines a new and powerful family of techniques --- called lifting theorems --- that have been developed in computational complexity theory. These new techniques have had a dazzling number of applications, leading to the resolution of a large number of hard problems in both computational complexity theory and discrete mathematics. Furthermore, they have revealed deep new connections between algorithms and proofs; showing that, in many cases of interests, algorithms are proofs and proofs are algorithms, and so analyzing one object allows us to analyze the other. The "lifting revolution" is far from being over and, in this proposal, we identify three concrete directions that we believe are ripe for attack with these new techniques. The first is deepening our understanding of algorithms commonly used in optimization; the second, in quantum computation; and the last, the theory of digital circuits (the same types of circuits that run your computer). Finally, we believe that a deeper --- and currently, only partially understood --- theory that explains the surprising breadth of these applications can also be developed, and indicate some promising work in this direction.
请考虑以下问题:给你一个非常大的数(比如10,000位),要求你找出除它的任何数(除了1或它本身)。2显然,这个问题对于强大的计算机来说是很难有效解决的。此外,现代世界的许多技术都依赖于这个问题难以解决的事实,因为它的硬度是密码学的基础,使我们所有的互联网通信安全! 这些关于计算任务的内在困难的问题是计算复杂性理论的研究,这是我的研究领域。在复杂性理论中,我们研究计算机执行计算所必须消耗的资源量,如运行时间、内存或能量。通过这种方式,计算复杂性是算法设计的硬币的另一面,算法设计关注的是为给定任务找到最有效的算法。这项研究计划概述了一个新的和强大的家庭的技术-所谓的提升定理-已在计算复杂性理论的发展。这些新技术已经有了令人眼花缭乱的应用数量,导致了大量的计算复杂性理论和离散数学的难题的解决。此外,它们揭示了算法和证明之间的深层新联系;表明在许多利益情况下,算法是证明,证明是算法,因此分析一个对象可以让我们分析另一个对象。“起重革命”远未结束,在本建议中,我们确定了三个具体的方向,我们认为这些新技术的攻击已经成熟。第一个是加深我们对优化中常用算法的理解;第二个是量子计算;最后一个是数字电路理论(与运行计算机的电路类型相同)。最后,我们相信还可以开发出一种更深入的(目前仅部分理解)理论来解释这些应用的惊人广度,并表明在这个方向上有一些有前途的工作。

项目成果

期刊论文数量(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 }}

Robere, Robert其他文献

Stabbing Planes
刺击飞机
  • DOI:
    10.48550/arxiv.1710.03219
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Beame, Paul;Fleming, Noah;Impagliazzo, Russell;Pankratov, Denis;Pitassi, Toniann;Robere, Robert
  • 通讯作者:
    Robere, Robert

Robere, Robert的其他文献

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

{{ truncateString('Robere, Robert', 18)}}的其他基金

Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPIN-2021-03036
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPAS-2021-00032
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPAS-2021-00032
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    DGECR-2021-00110
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Launch Supplement
Hardness Escalation: A New and Powerful Tool in Computational Complexity Theory
硬度升级:计算复杂性理论中的一个新的强大工具
  • 批准号:
    517234-2018
  • 财政年份:
    2019
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Postdoctoral Fellowships
Hardness Escalation: A New and Powerful Tool in Computational Complexity Theory
硬度升级:计算复杂性理论中的一个新的强大工具
  • 批准号:
    517234-2018
  • 财政年份:
    2018
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Postdoctoral Fellowships
A New Perspective on Computational Complexity
计算复杂性的新视角
  • 批准号:
    460219-2014
  • 财政年份:
    2016
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Doctoral
A New Perspective on Computational Complexity
计算复杂性的新视角
  • 批准号:
    460219-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Doctoral
A New Perspective on Computational Complexity
计算复杂性的新视角
  • 批准号:
    460219-2014
  • 财政年份:
    2014
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Doctoral
Analytical approach to combinatorial characterizations of computational dichotomies.
计算二分法组合表征的分析方法。
  • 批准号:
    415305-2011
  • 财政年份:
    2011
  • 资助金额:
    $ 3.35万
  • 项目类别:
    University Undergraduate Student Research Awards

相似海外基金

Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPIN-2021-03036
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPAS-2021-00032
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Sound in Space: towards a unified theory of auditory localization
空间声音:迈向听觉定位的统一理论
  • 批准号:
    RGPIN-2019-06121
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a unified theory for element uptake by minerals over the full range of element concentrations
建立矿物在整个元素浓度范围内吸收元素的统一理论
  • 批准号:
    RGPIN-2020-04173
  • 财政年份:
    2022
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a unified theory for element uptake by minerals over the full range of element concentrations
建立矿物在整个元素浓度范围内吸收元素的统一理论
  • 批准号:
    RGPIN-2020-04173
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    RGPAS-2021-00032
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
NSF-BSF: Small: AF: Towards a Unified Theory of Spanners
NSF-BSF:小:AF:迈向扳手的统一理论
  • 批准号:
    2121952
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Standard Grant
URoL:EN: Towards a unified theory of regulatory functions and networks across biological and social systems
URoL:EN:迈向跨生物和社会系统的监管功能和网络的统一理论
  • 批准号:
    2133863
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Continuing Grant
Towards a Unified Theory of Proof and Circuit Complexity
走向证明和电路复杂性的统一理论
  • 批准号:
    DGECR-2021-00110
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Launch Supplement
Sound in Space: towards a unified theory of auditory localization
空间声音:迈向听觉定位的统一理论
  • 批准号:
    RGPIN-2019-06121
  • 财政年份:
    2021
  • 资助金额:
    $ 3.35万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了