Grant: Discovery Grants Program - Individual

Computation is a fundamental concept. From biological and physical processes, to industry and commerce, it underlies much of our daily lives. Thus, it is highly important to understand which computational tasks can be easily computed, and which cannot. For example, modern cryptography -- which protects our every financial transaction -- relies on the unproven assumption that there are computational tasks for which solutions are easy to verify (given a purported solution, compute whether it indeed solves the task) but difficult to compute. Proving that such tasks exist (known as the P versus NP problem) is recognized by the Clay Mathematical Institute as one of the ten most important mathematical problems of our millennia, due to its profound importance to our understanding of computation. Two major approaches for resolving the P versus NP question are proof complexity which aims to show that there are theorems with no short proofs, and circuit complexity which aims to prove that there are computational tasks which require large hardware circuits. These are natural and important conjectures in their own right, and progress towards resolving these questions has led to a wide range of valuable and often surprising consequences. Examples include powerful tools for the analysis of algorithms, pseudo-randomness, machine learning, and faster algorithms for a variety of important tasks with practical applications. Recently, deep connections between the areas of proof and circuit complexity have emerged, enabling researchers to use tools from one area in order to make progress on the other. The discovery of these connections continues to revolutionize both areas, resolving a vast number of open problems in a relatively short time. Moreover, the consequences of these connections have also spilled over into related areas, becoming tremendously important tools for a wide variety of areas, including understanding the amount of information that must be communicated between two parties in order to solve a task, the relationships between total functions (TFNP), and secret sharing schemes in cryptography. However, many aspects of these connections -- in particular, their limitations and the full range of their applications -- are not well understood. This research program aims to develop a deeper understanding of the connections between proof and circuit complexity as a means of making progress towards major questions in these areas. Towards this, we will pursue two main goals. The first is to develop a more systematic understanding of when such connections occur, in order to understand their limitations. The second is to extend the tasks to which these connections can be applied in order to tackle important open problems in a variety of areas: proof complexity, the parallelizability of efficient algorithms, and the theory of efficiently verifiable total functions (TFNP).