Parallels Between Phase Transitions and Circuit Complexity?

Ankur Moitra Elchanan Mossel Colin Sandon

Published in: COLT (2020)

Keyphrases

phase transition
random constraint satisfaction problems
satisfiability problem
np complete
constraint satisfaction
random sat
computational complexity
high speed
combinatorial problems
deep structure
random instances
graph coloring
hard problems
orders of magnitude
decision problems