Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Lower Bounds for CSP Hierarchies Through Ideal Reduction

Conneryd, Jonas LU orcid ; Ghannane, Yassine and Pang, Shuo (2026) 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 2026-January. p.6436-6463
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].

Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
series title
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
editor
Larsen, Kasper Green and Saha, Barna
volume
2026-January
pages
28 pages
publisher
Association for Computing Machinery
conference name
37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
conference location
Vancouver, Canada
conference dates
2026-01-11 - 2026-01-14
external identifiers
  • scopus:105033685321
ISSN
1557-9468
1071-9040
ISBN
9781611978971
DOI
10.1137/1.9781611978971.231
language
English
LU publication?
yes
additional info
Publisher Copyright: Copyright © 2026 by SIAM.
id
01bd44f4-c2af-46a7-baf7-a97075db12b1
date added to LUP
2026-06-18 10:35:53
date last changed
2026-09-11 23:26:44
@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         = {{1557-9468}},
  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}},
}