22 citations · 30 across the 2 of their papers we have counts for
2 papers
cs.AI2005★ 22 cited
Hiding Satisfying Assignments: Two are Better than One
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-…
cond-mat.dis-nn2004★ 8 cited
How much backtracking does it take to color random graphs? Rigorous results on heavy tails
Haixia Jia, Cristopher moore
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants…