Lower Bounds for CSP Hierarchies Through Ideal Reduction

2025/11/21 by Jonas Conneryd, Conneryd, Jonas, Yassine Ghannane +3
Computer Science · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.2511.17272

Abstract

We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-reduction operators in the sense of Alekhnovich and Razborov [Proc. Steklov Inst. Math. 2003] can be used to fool the cohomological k-consistency algorithm. As applications, we prove optimal level lower bounds for c vs. ℓ-coloring for all ℓ ≥ c ≥ 3, and give a simplified proof of the lower bounds for lax and null-constraining CSPs of Chan and Ng [STOC 2025].

Citations

• On Approximability of Satisfiable k-CSPs: V
• Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
• The periodic structure of local consistency
• Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
• Better coloring of 3-colorable graphs
• Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
• Graphs with large girth and chromatic number are hard for Nullstellensatz
• Approximate Graph Colouring and the Crystal with a Hollow Shadow
• Cohomology in Constraint Satisfaction and Structure Isomorphism
• Sum-of-Squares Lower Bounds for Sparse Independent Set
• A Stress-Free Sum-of-Squares Lower Bound for Coloring
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• Proof Complexity Meets Algebra
• Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
• The Lov 'asz Theta Function for Random Regular Graphs and Community\n Detection in the Hard Regime
• A dichotomy theorem for nonuniform CSPs
• Sum of squares lower bounds for refuting any CSP
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
• Limitations of Algebraic Approaches to Graph Isomorphism Testing
• Sum of Squares Lower Bounds from Pairwise Independence
• On the chromatic number of random d-regular graphs
• On Systems of Linear Diophantine Equations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

Related

• Proof complexity of CSP
• New Bounds for the Ideal Proof System in Positive Characteristic
• On Approximability of Satisfiable k-CSPs: V
• Lower bounds for CSP refutation by SDP hierarchies
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems