Gödel and the Vicious Circle: On the (In)Feasibility of Lower Bounds | Richard M. Karp Distinguished Lecture

The NP != P conjecture states that short proofs of mathematical theorems are hard to find efficiently in general. It is often speculated that the conjecture has a self-referential nature: even if there was a relatively short proof of the conjecture itself, this proof might be hard to find. In the first part of this talk, Rahul Santhanam will discuss various situations in which the self-referentiality phenomenon for proving complexity lower bounds can be established formally, and will speculate on the extent to which this is a fundamental obstacle to attacking the P vs. NP problem and others of its kind.

Known proof-theoretic barriers to attacking NP vs. P and similar problems apply mostly to nonuniform lower bounds. In the second part of the talk, Santhanam will discuss a new approach to showing uniform lower bounds, which has already led to some progress on lower bounds for weak circuit classes. 

Rahul Santhanam is a professor in the Department of Computer Science at the University of Oxford, and a tutorial fellow at Magdalen College. He received his PhD from the University of Chicago, and taught at the University of Edinburgh after postdoctoral stints in Vancouver and Toronto, before moving to Oxford in 2016. He works across computational complexity theory, including in structural complexity, circuit complexity, proof complexity, foundations of cryptography, and learning theory. His recent research is mostly in the study of "meta-complexity" — i.e., the complexity of complexity, and its applications to various areas of computer science. 

===================================================================

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience. Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents [at] berkeley.edu with as much advance notice as possible.