Proof Complexity

Videos from BIRS Workshop 20w5144

, University of Washington
- 10:02
Proof Complexity 2020
Watch video | Download video: 202001200905-Beame.mp4 (205M)
, University of Toronto
- 10:56
Semialgebraic Proofs and Efficient Algorithm Design
Watch video | Download video: 202001201002-Fleming.mp4 (194M)
, University of Chicago
- 12:13
Hardness Condensation
Watch video | Download video: 202001201121-Razborov.mp4 (273M)
, University of Warsaw
- 16:29
Polynomial Calculus Space and Resolution Width
Watch video | Download video: 202001201600-Kolodziejczyk.mp4 (177M)
, Universitat Politècnica de Catalunya
- 16:56
Size-Degree Trade-Off for Sums-of-Squares Proofs
Watch video | Download video: 202001201630-Hakoniemi.mp4 (127M)
, Lund University
- 17:32
Dmitry Sokolov: (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables
Watch video | Download video: 202001201657-Sokolov.mp4 (168M)
, Mathematical Institute of the Czech Academy of Sciences
- 09:58
On Depth 1 Frege Systems
Watch video | Download video: 202001210902-Pudlak.mp4 (209M)
, Royal Holloway, University of London
- 11:01
and Edward Hirsch: Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?
Watch video | Download video: 202001211001-Hirsch.mp4 (223M)
, University of Oxford
- 11:50
Consistency of Circuit Lower Bounds with Bounded Theories
Watch video | Download video: 202001211122-CarboniOliveira.mp4 (104M)
, University of Oxford
- 12:20
Why are Proof Complexity Lower Bounds Hard?
Watch video | Download video: 202001211151-Pich.mp4 (108M)
, University of Jena
- 15:31
Characterising QBF Hardness via Circuit Complexity
Watch video | Download video: 202001211501-Beyersdorff.mp4 (100M)
, University of Chicago
- 16:31
Sum of Squares Bounds for the Ordering Principle
Watch video | Download video: 202001211601-Potechin.mp4 (161M)
, Università degli Studi di Roma La Sapienza
- 17:03
Resolution and the binary encodings of combinatorial principles
Watch video | Download video: 202001211632-Galesi.mp4 (131M)
, UC San Diego
- 17:31
The Surprising Power of Constant Depth Algebraic Proofs
Watch video | Download video: 202001211703-Mouli.mp4 (102M)
, Technion
- 09:54
Lifting in Proof Complexity
Watch video | Download video: 202001220902-Vinyals.mp4 (181M)
, Universitat Politecnica de Catalunya
- 10:45
Automating Resolution is NP-Hard
Watch video | Download video: 202001220955-Atserias.mp4 (200M)
, Stanford University
- 11:57
Automated Proof Search: The Aftermath
Watch video | Download video: 202001221111-Goos.mp4 (181M)
, Universitat Politecnica de Catalunya
- 09:31
Resolution Lower Bounds for Refutation Statements
Watch video | Download video: 202001230902-Garlik.mp4 (100M)
, UPC Universitat Politècnica de Catalunya
- 09:57
SETH and Resolution
Watch video | Download video: 202001230931-Bonacina.mp4 (134M)
, University of Ulm
- 10:29
Reversible Pebble Games and the Relation between Tree-like and General Resolution
Watch video | Download video: 202001230958-Toran.mp4 (120M)
, Steklov Institute of Mathematics at St. Petersburg
- 11:29
On 1-BP complexity of satisfiable Tseitin formulas and how it relates to regular resolution
Watch video | Download video: 202001231100-Itsykson.mp4 (99M)
, University of Chicago
- 11:52
k-Clique and Regular vs. General Resolution
Watch video | Download video: 202001231130-Pang.mp4 (84M)
, KTH Royal Institute of Technology
- 15:29
Exponential Resolution Lower Bounds for the Weak Pigeonhole Principle over Sparse Graphs
Watch video | Download video: 202001231501-Risse.mp4 (99M)
, Czech Academy of Sciences
- 16:31
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Watch video | Download video: 202001231601-deRezende.mp4 (92M)
, Università degli Studi di Roma La Sapienza
- 17:02
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
Watch video | Download video: 202001231632-Galesi.mp4 (121M)
, UC San Diego
- 17:35
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs
Watch video | Download video: 202001231704-Knop.mp4 (120M)
, Technion
- 10:00
Hard Examples for Common Variable Decision Heuristics
Watch video | Download video: 202001240934-Vinyals.mp4 (98M)