Lower Bounds for CSP Hierarchies Through Ideal Reduction
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. \(\ell\)-coloring for all \(\ell \ge c \ge 3\), and give a simplified proof of the lower bounds for lax and null-constraining CSPs of Chan and Ng [STOC 2025].
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Formal Methods in Verification
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 6436–6463
- Publication date
- 1 January 2026
- Language
- EN