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].

33 pages, to appear in SODA 2026