Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HIU TSUN NG:
All reports by Author Hiu Tsun Ng:

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