Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu +1

We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spi…