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

Revisions: 1

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