Proof Complexity
Videos from BIRS Workshop
Paul Beame, University of Washington
Monday Jan 20, 2020 09:05 - 10:02
Proof Complexity 2020
Noah Fleming, University of Toronto
Monday Jan 20, 2020 10:02 - 10:56
Semialgebraic Proofs and Efficient Algorithm Design
Alexander Razborov, University of Chicago
Monday Jan 20, 2020 11:21 - 12:13
Hardness Condensation
Leszek Kolodziejczyk, University of Warsaw
Monday Jan 20, 2020 16:00 - 16:29
Polynomial Calculus Space and Resolution Width
Tuomas Hakoniemi, Universitat Politècnica de Catalunya
Monday Jan 20, 2020 16:30 - 16:56
Size-Degree Trade-Off for Sums-of-Squares Proofs
Dmitry Sokolov, EPFL
Monday Jan 20, 2020 16:57 - 17:32
Dmitry Sokolov: (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables
Pavel Pudlak, Mathematical Institute of the Czech Academy of Sciences
Tuesday Jan 21, 2020 09:02 - 09:58
On Depth 1 Frege Systems
Iddo Tzameret, Royal Holloway, University of London
Tuesday Jan 21, 2020 10:01 - 11:01
and Edward Hirsch: Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?
Igor Carboni Oliveira, University of Oxford
Tuesday Jan 21, 2020 11:22 - 11:50
Consistency of Circuit Lower Bounds with Bounded Theories
Jan Pich, University of Oxford
Tuesday Jan 21, 2020 11:51 - 12:20
Why are Proof Complexity Lower Bounds Hard?
Olaf Beyersdorff, University of Jena
Tuesday Jan 21, 2020 15:01 - 15:31
Characterising QBF Hardness via Circuit Complexity
Aaron Potechin, University of Chicago
Tuesday Jan 21, 2020 16:01 - 16:31
Sum of Squares Bounds for the Ordering Principle
Nicola Galesi, Università degli Studi di Roma La Sapienza
Tuesday Jan 21, 2020 16:32 - 17:03
Resolution and the binary encodings of combinatorial principles
Sasank Mouli, UC San Diego
Tuesday Jan 21, 2020 17:03 - 17:31
The Surprising Power of Constant Depth Algebraic Proofs
Marc Vinyals, Technion
Wednesday Jan 22, 2020 09:02 - 09:54
Lifting in Proof Complexity
Albert Atserias, Universitat Politecnica de Catalunya
Wednesday Jan 22, 2020 09:55 - 10:45
Automating Resolution is NP-Hard
Mika Goos, Stanford University
Wednesday Jan 22, 2020 11:11 - 11:57
Automated Proof Search: The Aftermath
Michal Garlík, Universitat Politecnica de Catalunya
Thursday Jan 23, 2020 09:02 - 09:31
Resolution Lower Bounds for Refutation Statements
Ilario Bonacina, UPC Universitat Politècnica de Catalunya
Thursday Jan 23, 2020 09:31 - 09:57
SETH and Resolution
Jacobo Toran, University of Ulm
Thursday Jan 23, 2020 09:58 - 10:29
Reversible Pebble Games and the Relation between Tree-like and General Resolution
Dmitry Itsykson, Steklov Institute of Mathematics at St. Petersburg
Thursday Jan 23, 2020 11:00 - 11:29
On 1-BP complexity of satisfiable Tseitin formulas and how it relates to regular resolution
Shuo Pang, University of Chicago
Thursday Jan 23, 2020 11:30 - 11:52
k-Clique and Regular vs. General Resolution
Kilian Risse, KTH Royal Institute of Technology
Thursday Jan 23, 2020 15:01 - 15:29
Exponential Resolution Lower Bounds for the Weak Pigeonhole Principle over Sparse Graphs
Susanna de Rezende, Czech Academy of Sciences
Thursday Jan 23, 2020 16:01 - 16:31
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Nicola Galesi, Università degli Studi di Roma La Sapienza
Thursday Jan 23, 2020 16:32 - 17:02
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
Alexander Knop, UC San Diego
Thursday Jan 23, 2020 17:04 - 17:35
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs
Marc Vinyals, Technion
Friday Jan 24, 2020 09:34 - 10:00
Hard Examples for Common Variable Decision Heuristics
