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年以来电路下界的主要问题之一。其次，这个项目介绍了一种新的方法来证明下界对常数深度电路计数门，这是另一个主要问题的电路复杂性。最后，该项目将使用电路复杂性的技术来构建最基本的加密原语的弱版本，即单向函数（尽管付出了很大努力，但甚至不知道存在）。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。