#### Alladi Ramakrishnan Hall

#### Godel's Theorem and Propositional Proof Complexity

#### Rahul Santhanam

##### Oxford, UK

*A classical result of Godel states that for any 'rich enough' consistent first-order theory T of arithmetic, there are statements that are true in the natural numbers but are unprovable in T.*

Are there analogues of this result for the finitistic setting of propositional proof complexity? And might such analogues have implications for the hardness of showing complexity lower bounds?

I will discuss some recent results with Jan Pich on these questions.

Done