CAREER: Lower Bounds for 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.