6 papers
Super Solutions of the Model RB
Guangyan Zhou, Wei Xu
The concept of super solution is a special type of generalized solutions with certain degree of robustness and stability. In this paper we consider the -super solutions of t…
Hiding solutions in model RB: Forced instances are almost as hard as unforced ones
Guangyan Zhou
In this paper we study the forced instance spaces of model RB, where one or two arbitrary satisfying assignments have been imposed. We prove rigorously that the expected number of…
Exact Phase Transitions of Model RB with Slower-Growing Domains
Jun Liu, Ke Xu, Guangyan Zhou
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…
The random 2-SAT partition function
Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth +4
We show that throughout the satisfiable phase the normalised number of satisfying assignments of a random -SAT formula converges in probability to an expression predicted by the…
Widely distributed clusters of the constraint satisfaction problem model d-k-CSP
Wei Xu, Fuzhou Gong, Guangyan Zhou
Relation between problem hardness and solution space structure is an important research aspect. Model d-k-CSP generates very hard instances when and is near 1, where …
A sharp threshold of propagation connectivity for mixed random hypergraphs
Guangyan Zhou, Bin Wang, Ke Xu
This paper studies the propagation connectivity of a random hypergraph containing both 2-edges and 3-hyperedges. We find an exact threshold of the propagation connecti…