CAREER: Lower Bounds for Shallow Circuits

职业生涯：浅层电路的下限

• 批准号: 2338730
• 负责人: Aleksandr Golovnev
• 金额: $ 64.5万
• 依托单位: Georgetown University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-03-15 至 2029-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2338730&HistoricalAwards=false
• 关键词: CAREER; Lower; Bounds; Shallow; Circuits

Circuit complexity is a fundamental area in computer science and mathematics. The applications of circuit complexity span fields as diverse as cryptography, algorithms, discrete mathematics, and software verification. The ultimate goal of this area is to prove that certain functions of interest cannot be computed efficiently. As partial progress towards this goal, a number of results have been proven for restricted models of computation, which has resulted in numerous applications to cryptography and computer science in general. This project aims to prove strong new results on the limits of efficient computation, improving and generalizing the results of the last few decades. Through the integrated research and educational activities, students will learn about a key tool for circuit complexity, matrix rigidity, in a new graduate course. The general interest of students in theoretical computer science will be raised by a new course "Gems in Theoretical Computer Science". Outreach beyond the institution will be achieved via a Coursera course sequence. Specifically, this project seeks to revive progress in three important directions in circuit complexity. First, the project will study explicit constructions of rigid matrices. Such constructions will ideally lead us to a better understanding of the power and limitations of logarithmic-depth circuits, one of the major problems in circuit lower bounds since 1977. Second, this project introduces a new approach to proving lower bounds against constant-depth circuits with counting gates, which is another major problem in circuit complexity. Finally, this project will use the techniques from circuit complexity to construct a weak version of the most fundamental cryptographic primitive, a one-way function (which, despite much effort, is not even known to exist).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.

电路复杂性是计算机科学和数学的基本领域。电路复杂度的应用范围跨越了密码学，算法，离散数学和软件验证的多样化。该领域的最终目标是证明无法有效地计算某些感兴趣的功能。作为朝着这一目标的部分进展，已经证明了许多结果的计算模型，这导致了对密码学和计算机科学的多种应用。该项目旨在证明有效计算的局限性，改善和推广过去几十年的结果。通过综合的研究和教育活动，学生将在新的研究生课程中了解电路复杂性，矩阵刚度的关键工具。学生对理论计算机科学的普遍兴趣将由新课程“理论计算机科学中的宝石”提出。超越机构的外展将通过Coursera课程序列实现。具体而言，该项目试图在电路复杂性的三个重要方向上恢复进展。首先，该项目将研究刚性矩阵的明确结构。理想情况下，这种结构将使我们更好地理解对数深度电路的功率和局限性，这是自1977年以来电路下限的主要问题之一。其次，该项目引入了一种新的方法来证明与计数gates的恒定深度电路证明下限，这是电路复杂性的另一个主要问题。最后，该项目将利用电路复杂性的技术来构建最基本的加密原始功能的弱版本，即单向功能（尽管努力，甚至还不存在，但它都不存在）。该奖项反映了NSF的法定任务，并认为通过基金会的智力智力和更广泛的影响，可以通过评估来审查CRITERIA。