Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=dYMPRGQheow


Duration: 29:21
261 views
3

Shuo Pang (University of Copenhagen)
https://simons.berkeley.edu/talks/shuo-pang-university-copenhagen-2023-04-18
Satisfiability: Theory, Practice, and Beyond

We prove that polynomial calculus and hence also Nullstellensatz requires linear degree
to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size.



Other Videos By Simons Institute for the Theory of Computing


2023-04-21MCSat Approaches for Solving Non-linear Modular Arithmetic
2023-04-21Reactive Synthesis Empowered by Logical Reasoning
2023-04-20The Power of Extended Resolution: A Practitioner's Perspective
2023-04-20Exploiting Combinatorial Structure in Constraint Programming: ...
2023-04-20Benefits of Abstract Modelling using Conjure
2023-04-20Exact Covering with Colours
2023-04-20Rado numbers: SAT methods and connections to Nullstellensatz complexity
2023-04-20Modern Constraint Programming, For People Who Know SAT
2023-04-20ASP: Theory, Practice, and Beyond
2023-04-19Logic, Optimization, and Constraint Programming: A Fruitful Collaboration
2023-04-19Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
2023-04-19Clique is hard on average for unary Sherali-Adams
2023-04-19Theoretical limits of 1UIP Learning
2023-04-19The Proof Complexity of Integer Programming
2023-04-19The Power of Unentangled Quantum Proofs With Non-negative Amplitudes | Quantum Colloquium
2023-04-19Beyond SAT - Proofs for QBF, and more
2023-04-19Isomorph-Free Generation Of Combinatorial Objects With Sat Modulo Symmetries
2023-04-18A Roadmap for the Next Phase of SAT Research
2023-04-18Structure-guided Local Improvement for Maximum Satisfiability
2023-04-18Designing Samplers is Easy: The Boon of Testers
2023-04-18IPASIR-UP: User Propagators for CDCL


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Satisfiability: Theory Practice and Beyond
Daniel Hsu