15 citations · 17 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2003★ 15 cited
Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances
Ke Xu, Wei Li
This paper first analyzes the resolution complexity of two random CSP models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the thres…
cs.CC2000
An Average Analysis of Backtracking on Random Constraint Satisfaction Problems
Ke Xu, Wei Li
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. It is proved that Model GB in which each constraint is easy to…