CAREER: Lower Bounds for Shallow Circuits

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

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.