@inproceedings{01bd44f4-c2af-46a7-baf7-a97075db12b1,
  abstract     = {{<p>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].</p>}},
  author       = {{Conneryd, Jonas and Ghannane, Yassine and Pang, Shuo}},
  booktitle    = {{Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026}},
  editor       = {{Larsen, Kasper Green and Saha, Barna}},
  isbn         = {{9781611978971}},
  issn         = {{1071-9040}},
  language     = {{eng}},
  pages        = {{6436--6463}},
  publisher    = {{Association for Computing Machinery}},
  series       = {{Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms}},
  title        = {{Lower Bounds for CSP Hierarchies Through Ideal Reduction}},
  url          = {{http://dx.doi.org/10.1137/1.9781611978971.231}},
  doi          = {{10.1137/1.9781611978971.231}},
  volume       = {{2026-January}},
  year         = {{2026}},
}