On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.
Suprovat GhoshalEuiwoong LeePublished in: FOCS (2023)
Keyphrases
- constraint satisfaction problems
- constraint propagation
- constraint satisfaction
- hard constraints
- wavelet transform
- phase transition
- np complete
- information theoretic
- constrained problems
- linear systems
- search space
- non binary
- mixed integer
- np hard
- neural network
- sat problem
- symmetry breaking
- hypertree decomposition
- worst case
- special case
- computational complexity
- objective function
- multiscale