Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

Jin-Yi Cai Xi Chen Heng Guo Pinyan Lu

Published in: COCOA (2012)

Keyphrases

phase transition
constraint satisfaction
random constraint satisfaction problems
satisfiability problem
hard problems
dynamic programming
constraint satisfaction problems
cellular automata
heuristic search
combinatorial problems
sat problem
sat instances
graph coloring
random instances
average degree