Jonas Conneryd: Lower Bounds for CSP Hierarchies Through Ideal Reduction

Abstract:

We prove that the cohomological k-consistency algorithm does not solve c vs. \(\ell\)-coloring on n-vertex graphs, for any \(\ell \geq c \geq 3\) and \(k \leq \Omega(n)\). We obtain our results through a novel connection to degree lower bounds for algebraic proof systems, which we hope will have further applications.