Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses.
Chris JonesKunal MarwahaJuspreet Singh SandhuJonathan ShiPublished in: ITCS (2023)
Keyphrases
- constraint satisfaction problems
- random instances
- phase transition
- constraint satisfaction
- np hard
- ordering heuristics
- np complete
- randomly generated
- binary csps
- maintaining arc consistency
- arc consistency
- easy hard easy pattern
- information theoretic
- computational complexity
- learning theory
- worst case
- constraint networks
- uniformly distributed
- soft constraints
- tree decomposition
- constraint problems
- decision diagrams
- special case
- search space
- partial constraint satisfaction
- lower bound
- objective function