About
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?
Chairs/Organizers
Invited Participants
Robert Andrews (University of Illinois at Urbana-Champaign), Benny Applebaum (Tel-Aviv University), Shai Ben-David (University of Waterloo), Markus Bläser (Universität des Saarlandes), Igor Carboni Oliveira (University of Warwick), Prerona Chatterjee (Institute of Mathematics of the Czech Academy of Sciences), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Pranjal Dutta (Chennai Mathematical Institute), Noah Fleming (Memorial University), Nashlen Govindasamy (Imperial College London), Mika Göös (EPFL), Tim Hoffmann (University of Jena (FSU)), Rahul Ilango (MIT), Russell Impagliazzo (UC San Diego), Dmitry Itsykson (Steklov Institute of Mathematics at St.Petersburg.), Abhishek Jain (Johns Hopkins University), Emil Jeřábek (Czech Academy of Sciences), Zhengzhong Jin (MIT), Erfan Khaniki (Charles University), Ján Pich (Oxford University), Pavel Pudlák (Czech Academy of Sciences), Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai), Anastasia Sofronova (St. Petersburg State University), Anamay Gurunath Tengse (University of Haifa), Iddo Tzameret (Imperial College London)