Proof Complexity and Meta-Mathematics
Organizers:
One of the main motivations for proof complexity is meta-mathematics: understanding how hard mathematical theorems are to prove. In complexity theory, we are especially motivated to understand the meta-mathematics of complexity lower bounds, and therefore meta-complexity is obviously relevant here. This workshop will focus on questions such as: Are there further barriers to lower bounds beyond the natural proofs, relativization, and algebrization barriers? What formal connections can we show between proof complexity and circuit complexity, and what does this imply for the meta-mathematics of circuit lower bounds? What is the strongest propositional proof system for which we can show that all truth table tautologies are hard? Is bounded-depth Frege hard to automate? Is there a formal connection between learning and automatability?
Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.
Further details about this workshop will be posted in due course. To contact the organizers about this workshop, please complete this form.
Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.
