All lectures are in Pacific Time and are subject to change.

 

Monday: Proof Complexity

Tuesday: Meta-Mathematics of Complexity

Wednesday: Algebraic Approaches to Barriers and Proofs

Thursday: Satisfiability & Applications

Friday: Independence, Reflection and More

–
Coffee and Check-In
–
Opening Remarks
–
Lower Bounds Against PC With Extension Variables
Russell Impagliazzo (UCSD)
–
Break
–
Random log(n)-CNF are Hard for Cutting Planes (Again)
Dmitry Sokolov (EPFL)
–
Lunch
–
The Hitting Proof System
Yuval Filmus (Technion)
–
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
Anastasia Sofronova (EPFL)
–
Break
–
Lifting to Parity Decision Trees via Stifling (with applications to proof complexity)
Suhail Sherif (University of Toronto)
–
Reception
–
Coffee and Check-In
–
Consistency of NEXP Not in P/poly in a Strong Theory
Albert Atserias (Technical University of Catalonia (UPC))
–
Break
–
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Igor Oliveira (University of Warwick)
–
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Rahul Ilango (MIT)
–
Lunch
–
Towards P≠NP from Extended Frege Lower Bounds
Ján Pich (University of Oxford)
–
Break
–
Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
Zhengzhong Jin (MIT)
–
Coffee and Check-In
–
Frontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
Iddo Tzameret (Imperial College London)
–
Break
–
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
Markus Bläser (Saarland University)
–
Lunch
–
Natural Proofs in Algebraic Circuit Complexity
Anamay Tengse (University of Haifa)
–
Break
–
Lower Bounds Against Non-Commutative Models of Algebraic Computation
Prerona Chatterjee (Tel Aviv University)
–
On the Problems Related to Waring Rank and Border Waring Rank
Pranjal Dutta (National University of Singapore)
–
Coffee and Check-In
–
On Cutting Planes Proofs with Strengthening Rules
Jakob Nordström (University of Copenhagen)
–
Break
–
On the Dominance-Based Strengthening Rule
Neil Thapen (Institute of Mathematics, Czech Academy of Sciences)
–
Connections Between QBF Proof Complexity and Circuit Complexity
Olaf Beyersdorff (Friedrich Schiller University Jena)
–
Lunch
–
Weak Versions of Extended Resolution
Emre Yolcu (CMU)
–
CDCL vs Resolution: The Picture in QBF
Benjamin Böhm (University of Jena)
–
Break
–
Read-Once Branching Programs as Proof Lines
Dmitry Itsykson (Ben-Gurion University of the Negev)
–
Open Problem Session
–
Coffee and Check-In
–
Unprovability and Other Impossibility Results in Machine Learning
Shai Ben-David (University of Waterloo)
–
Break
–
Implicit Proof Systems
Pavel Pudlák (Academy of Sciences of the Czech Republic)
–
Lower Bounds for NW-generators in AC0-Frege
Erfan Khaniki (Charles University Prague)
–
Lunch
–
TFNP
Noah Fleming (University of Toronto)
Register

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. 

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials. 

Register Now