Revision #1 Authors: Siu On Chan, Hiu Tsun Ng, Sijin Peng

Accepted on: 13th May 2024 19:35

Downloads: 7

Keywords:

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), affine integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound for approximate graph coloring was given by Ciardo and Živný (STOC 2023).

We prove the first linear (and hence optimal) level lower bound for LP+AIP and its stronger variant, SDP+AIP. For each hierarchy, our bound holds for random instances of a broad class of CSPs that we call $\tau$-wise neutral. We extend to other hierarchies the LP lower bound techniques in Benabbas, Georgiou, Magen and Tulsiani (ToC 2012) and Kothari, Mori, O’Donnell, and Witmer (STOC 2017), and simplify the SDP solution construction in the latter.

Fixed mistakes in Section 7 about the AIP scheme

TR24-066 Authors: Siu On Chan, Hiu Tsun Ng, Sijin Peng

Publication: 8th April 2024 22:03

Downloads: 160

Keywords:

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), afinfe integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound for approximate graph coloring was given by Ciardo and Živný (STOC 2023).

We prove the first linear (and hence optimal) level lower bound for LP+AIP and its stronger variant, SDP+AIP. For each hierarchy, our bound holds for random instances of a broad class of CSPs that we call ?-wise neutral. We extend to other hierarchies the LP lower bound techniques in Benabbas, Georgiou, Magen and Tulsiani (ToC 2012) and Kothari, Mori, O’Donnell, and Witmer (STOC 2017), and simplify the SDP solution construction in the latter.