Sasha Razborov: Grand Challanges in Complexity Theory through the Lens of Proof Theory

Abstract: Given our current inability to even formulate a coherent program towards
solving grand challenges in computational complexity (such as P vs. NP), it
becomes increasingly important to at least understand this state of affairs;
such attempts are often called ``barriers''. The proof-theoretic approach
tries to rule out the existence of solutions within a class of methods that
is both rigorously defined and reasonably large, in the hope that this will
give at least some insight into the nature of the difficulties. It turns out
that this approach becomes most successful when the class of methods
inherently involves, explicitly or implicitly, computational concepts similar
to those it intends to study. One framework where this hope has materialized
is called Natural Proofs, and the parallel framework in which the
corresponding problems are largely open is that of (propositional) proof
complexity.

The main purpose of this talk is to give an accessible introduction to this
kind of problems, in the hope of attracting to them new generation of
researchers.