Workshops

Spring 2023

Proof Complexity and Meta-Mathematics

Mar 20, 2023 to Mar 24, 2023

Return to event »

Monday, March 20th, 2023
9:00 am–9:40 am		Coffee and Check-In
9:40 am–9:45 am		Opening Remarks
9:45 am–10:30 am		Lower Bounds Against PC With Extension Variables Russell Impagliazzo (UCSD)
10:30 am–11:00 am		Coffee Break
11:00 am–12:00 pm		Random log(n)-CNF are Hard for Cutting Planes (Again) Dmitry Sokolov (EPFL)
12:00 pm–2:00 pm		Lunch (on your own)
2:00 pm–2:30 pm		The Hitting Proof System Yuval Filmus (Technion)
2:30 pm–3:00 pm		A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion Anastasia Sofronova (EPFL)
3:00 pm–3:30 pm		Coffee Break
3:30 pm–4:30 pm		Lifting to Parity Decision Trees via Stifling (with applications to proof complexity) Arkadev Chattopadhyay (Tata Institute of Fundamental Research)
4:30 pm–5:30 pm		Light Reception

Tuesday, March 21st, 2023
9:00 am–9:45 am		Coffee and Check-In
9:45 am–10:30 am		Consistency of NEXP Not in P/poly in a Strong Theory Albert Atserias (Technical University of Catalonia (UPC))
10:30 am–11:00 am		Coffee Break
11:00 am–11:30 am		Unprovability of Complexity Bounds in Bounded Arithmetic Igor Oliveira (University of Warwick)
11:30 am–12:00 pm		Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic Rahul Ilango (MIT)
12:00 pm–2:00 pm		Lunch (on your own)
2:00 pm–3:00 pm		Towards P≠NP from Extended Frege Lower Bounds Ján Pich (University of Oxford)
3:00 pm–3:30 pm		Coffee Break
3:30 pm–4:30 pm		Indistinguishability Obfuscation via Mathematical Proofs of Equivalence Zhengzhong Jin (MIT)

Wednesday, March 22nd, 2023
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		Frontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems Iddo Tzameret (Imperial College London)
10:30 am–11:15 am		Coffee Break
11:15 am–12:00 pm		Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory Markus Bläser (Saarland University)
12:00 pm–2:00 pm		Lunch (on your own)
2:00 pm–2:45 pm		Natural Proofs in Algebraic Circuit Complexity Anamay Tengse (University of Haifa)
2:45 pm–3:30 pm		Coffee Break
3:30 pm–4:00 pm		Lower Bounds Against Non-Commutative Models of Algebraic Computation Prerona Chatterjee (Tel Aviv University)
4:00 pm–4:30 pm		On the Problems Related to Waring Rank and Border Waring Rank Pranjal Dutta (National University of Singapore)

Thursday, March 23rd, 2023
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:30 am		On Cutting Planes Proofs with Strengthening Rules Jakob Nordström (University of Copenhagen)
10:30 am–11:00 am		Coffee Break
11:00 am–11:30 am		On the Dominance-Based Strengthening Rule Neil Thapen (Institute of Mathematics, Czech Academy of Sciences)
11:30 am–12:00 pm		Connections Between QBF Proof Complexity and Circuit Complexity Olaf Beyersdorff (Friedrich Schiller University Jena)
12:00 pm–2:00 pm		Lunch (on your own)
2:00 pm–2:30 pm		Weak Versions of Extended Resolution Emre Yolcu (CMU)
2:30 pm–3:00 pm		CDCL vs Resolution: The Picture in QBF Benjamin Böhm (University of Jena)
3:00 pm–3:30 pm		Coffee Break
3:30 pm–4:00 pm		Read-Once Branching Programs as Proof Lines Dmitry Itsykson (Ben-Gurion University of the Negev)
4:00 pm–4:45 pm		Open Problem Session

Friday, March 24th, 2023
9:00 am–9:45 am		Coffee and Check-In
9:45 am–10:30 am		Unprovability and Other Impossibility Results in Machine Learning Shai Ben-David (University of Waterloo)
10:30 am–11:00 am		Coffee Break
11:00 am–11:30 am		Implicit Proof Systems Pavel Pudlák (Academy of Sciences of the Czech Republic)
11:30 am–12:00 pm		Lower Bounds for NW-generators in AC0-Frege Erfan Khaniki (Charles University)
12:00 pm–2:00 pm		Lunch (on your own)
2:00 pm–2:45 pm		TFNP Noah Fleming (University of Toronto)