How Random CSPs Fool Hierarchies: II

Relaxations for the constraint satisfaction problem (CSP) include bounded width (BW), linear program (LP), semidefinite program (SDP), affine integer program (AIP), and their combinations. Tightening relaxations systematically leads to hierarchies and stronger algorithms. For LP+AIP and SDP+AIP hierarchies, various lower bounds were shown by Ciardo and Živný (STOC 2023, STOC 2024) and by Chan, Ng, and Peng (STOC 2024).

This paper continues on this line of work to show lower bounds for related hierarchies. We prove new lower bounds to BW and AIP hierarchies. We also show the first lower bounds to the cohomological consistency hierarchy of Ó Conghaile (MFCS 2022) and the C(BLP+AIP) hierarchy of Ciardo and Živný (SODA 2022). Our lower bounds are for linear level and optimal. They make partial progress towards an open question of Lichter and Pago (arXiv 2407.09097v1) concerning the power of these hierarchies.

We prove our results using new closure and boundary. We generalize closure and boundary to streamline proofs across hierarchies.