CAREER: Lower Bounds for Shallow Circuits

电路复杂性是计算机科学和数学的一个基础领域。电路复杂性的应用领域包括密码学、算法、离散数学和软件验证等。这一领域的最终目标是证明某些感兴趣的函数不能有效地计算。随着实现这一目标的部分进展，已经证明了一些限制计算模型的结果，这导致了密码学和计算机科学的许多应用。该项目旨在证明关于高效计算极限的强有力的新结果，改进和推广过去几十年的结果。通过综合研究和教育活动，学生将在新的研究生课程中学习电路复杂性的关键工具——矩阵刚性。新开设的“理论计算机科学中的宝石”课程将提高学生对理论计算机科学的普遍兴趣。学院之外的拓展将通过Coursera的课程序列来实现。具体来说，这个项目寻求在电路复杂性的三个重要方向上恢复进展。首先，该项目将研究刚性矩阵的显式结构。这种结构将理想地引导我们更好地理解对数深度电路的能力和局限性，这是自1977年以来电路下界的主要问题之一。其次，该项目引入了一种新的方法来证明具有计数门的等深度电路的下界，这是电路复杂性的另一个主要问题。最后，这个项目将使用电路复杂性的技术来构建一个最基本的加密原语的弱版本，一个单向函数（尽管付出了很多努力，但它甚至不知道存在）。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.