Exact Phase Transitions of Model RB with Slower-Growing Domains
This work provides incremental improvements in theoretical computer science by offering tighter bounds for phase transitions in constraint satisfaction problems, which is important for researchers in algorithms and complexity theory.
The paper tackles the challenge of precisely determining phase transitions in random RB constraint satisfaction problems by applying a refined second moment method, achieving exact phase transition results under more relaxed conditions, particularly with slower-growing domain sizes.
The second moment method has always been an effective tool to lower bound the satisfiability threshold of many random constraint satisfaction problems. However, the calculation is usually hard to carry out and as a result, only some loose results can be obtained. In this paper, based on a delicate analysis which fully exploit the power of the second moment method, we prove that random RB instances can exhibit exact phase transition under more relaxed conditions, especially slower-growing domain size. These results are the best by using the second moment method, and new tools should be introduced for any better results.