Proof Complexity: From Theoretical Roots to Fertile Forest
Thursday, November 21, 2024, 11 A.M.
Bahen Centre for Information Technology, BA 3200
This lecture is open to the public. No registration is required, but space is limited.
Abstract:
One common view of proofs is an excessively formal set of rules that one must figure out how to apply in order to prove or derive something that is obvious in the first place. In this talk I will present proof complexity from a personal perspective, and will argue that proof systems are natural, and essential for understanding algorithms and the limits of computation. I will provide examples showing that proof systems hide behind many fundamental problems in mathematics and computer science, and how the intrinsic difficulty of the underlying problem is closely mirrored by the inherent complexity of their associated proofs. We will then see how Cook and Reckhow’s seminal paper from 1979 gave rise to proof complexity as a discipline, and revealed the fundamental connection between proof complexity and the P versus NP problem. I will highlight some of the major discoveries that have been made, with a focus on new results and exciting connections that have been made with other areas in the last 10-20 years. These new connections have enabled breakthrough discoveries in several areas, including: algorithms for solving distributional learning problems, connections with total NP search problems (TFNP), approximation algorithms, circuit lower bounds, cryptography (secret sharing schemes), and error correcting codes.
This talk will be tutorial in style and is intended for people working in related areas who may not be familiar with proof complexity. Moreover, since proof complexity has its roots at the University of Toronto, this will also be an opportunity to celebrate 60 years of a truly outstanding department.
Bio:
Toniann Pitassi is the Jeffrey L. and Brenda Bleustein Professor of Computer Science at Columbia University, and also a professor of Computer Science at the University of Toronto where she is currently on leave. Pitassi received her bachelor’s degree from Penn State, and her PhD from the University of Toronto, where she was lucky to be supervised by Stephen Cook. She has previously held positions at UCSD, University of Pittsburgh, University of Arizona, and the Institute for Advanced Study. Pitassi’s primary research area is complexity theory and proof complexity, which aim to understand the limits of proofs and computation. More recently her research interests have expanded to include theoretical aspects of machine learning, privacy and fairness, and whatever her graduate students are interested in. Pitassi was an invited speaker at the International Congress of Mathematicians in Berlin in 1998. Her recent honours include the EATCS (European Association for Theoretical Computer Science) distinguished research award (2021), fellow of the ACM (2018), and member of the National Academy of Sciences (2022).