Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
summary
Proves that polynomial calculus and Nullstellensatz require linear degree (hence a strongly exponential-size lower bound) to refute that sparse random d-regular and sparse Erdős–Rényi graphs are 3-colourable, with degree linear in n; builds a dual linear map by piecing local reduction operators over a family of closed sets (closures of small vertex sets), uses a Grobner/Buchberger-style local-to-global criterion, a special vertex ordering and sparsity/pseudorandom lemmas, and shows the closure sizes stay small so the construction succeeds.
AI-written summary · about
chapters (7)
- 0:00Introduction to the problem
- 4:52Problem encoding in PC
- 6:55Polynomial calculus framework
- 12:29Proving degree lower bounds
- 18:37Construction for coloring
- 23:59Applying the lower bound
- 26:09Conclusion and open problems
related talks
24mA New Conjecture on Hardness of Low-Degree 2-CSP’s with...
01h 09mPlenary: Neighborhoods Banding Together: Reasoning Globally about Programs
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
18mOn the Verification of a Subgraph Construction Algorithm
53mData Deduplication For Redundant Graph Structures Files
24mPolynomial-Time Program Equivalence for Machine Knitting
32mSynthesis, Simplification and Analysis of Biological Networks Using Higher Order Topological Connect
20mSimple and Efficient Computation of Minimal Weak Control Closure