Exact Phase Transitions of Model RB with Slower-Growing Domains

The study of random constraint satisfaction problems (CSPs) has received tremendous ideas from combinatorics, computer science and statistical physics. Random CSPs contain a large set of variables which interact through a large set of constraints, where each variable ranges over a domain and a configuration (solution) to all the variables should satisfy all of the constraints. A fundamental question in the study of random CSPs is the average-case computational complexity of solving ensembles of CSPs. Great amount of theoretical and algorithmic work has been devoted to establish and locate the satisfiability threshold, and studies show that complexity attains the maximum at the SAT-UNSAT transition. Many of the studied CSP models (such as random k-SAT, graph coloring) have fixed domain size, constraint length, and the number of constraints is linear compared with the number of variables. In recent years, a lot of attention has been paid to the study of CSPs with growing domains or constraint length ([13, 7, 4, 5]).