Seminar

Registration required to attend in-person or to receive Zoom link

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 non-uniform 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 Professor in the Department of Computer Science at the University of Oxford, and 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.