Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SIJIN PENG:
All reports by Author Sijin Peng:

TR24-066 | 29th March 2024
Siu On Chan, Hiu Tsun Ng, Sijin Peng

How Random CSPs Fool Hierarchies

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 ... more >>>




ISSN 1433-8092 | Imprint