Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-066 | 13th May 2024 19:35

How Random CSPs Fool Hierarchies

RSS-Feed




Revision #1
Authors: Siu On Chan, Hiu Tsun Ng, Sijin Peng
Accepted on: 13th May 2024 19:35
Downloads: 7
Keywords: 


Abstract:

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.



Changes to previous version:

Fixed mistakes in Section 7 about the AIP scheme


Paper:

TR24-066 | 29th March 2024 17:41

How Random CSPs Fool Hierarchies





TR24-066
Authors: Siu On Chan, Hiu Tsun Ng, Sijin Peng
Publication: 8th April 2024 22:03
Downloads: 160
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint