Speaker: Jan Pich, University of Toronto
Title: Complexity Theory in Bounded Arithmetic
We will discuss the provability of complexity theoretic conjectures in weakfragments of arithmetic like Cook's theory PV. These theories are actuallyquite powerful in the sense that they can formalize a lot of computationalcomplexity, e.g. PV proves the PCP theorem. However, to prove a statement in such a theory one typically needs to provide an efficient algorithm witnessing its existential quantifiers. In some cases this might lead to acontradiction. Notably, the question whether such a witnessing exists isoften of independent interest.In this talk we will focus on circuit lower bounds. It is not known how toshow that polynomial circuit lower bounds for SAT are unprovable in PV butunder certain hardness assumptions we can obtain the unprovability essentially for any theory weaker than PV (in terms of provably total functions). Unconditionally quasipolynomial circuit lower bounds for SAT are unprovablein the theory V0.