Near-Optimal UGC-hardness of Approximating Max k-CSP_R.
Pasin ManurangsiPreetum NakkiranLuca TrevisanPublished in: APPROX-RANDOM (2016)
Keyphrases
- constraint satisfaction problems
- random instances
- phase transition
- np complete
- constraint satisfaction
- ordering heuristics
- user generated content
- maintaining arc consistency
- np hard
- arc consistency
- constraint propagation
- computational complexity
- randomly generated
- decomposition methods
- information theoretic
- tree decompositions
- tree decomposition
- constraint solving
- learning theory
- constraint networks
- constraint programming
- decomposition method
- satisfiability problem
- hard problems
- constraint problems
- constraint graph
- parametric curves
- closest string
- social networks
- neural network