13 citations · 13 across the 7 of their papers we have counts for
7 papers
Solution independence and self-referential instances
Guangyan Zhou, Bin Wang, Jianxin Wang +1
In this paper, we investigate the hitting set problem and demonstrate that solution independence is the crucial property underlying the construction of self-referential instances.…
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…