The SAT–UNSAT transition for random constraint satisfaction problems

We study threshold phenomena for a large class of random constraint satisfaction problems over finite domains. Our main contribution is a complete classification of the nature (sharp or coarse) of the SAT–UNSAT transition for random Boolean CSPs, which is based on easily decidable properties.