22 citations · 50 across the 4 of their papers we have counts for
4 papers
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-…
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Haixia Jia, Cristopher Moore, Doug Strain
To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is…
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…
From spin glasses to hard satisfiable formulas
Haixia Jia, Cristopher Moore, Bart Selman
We introduce a highly structured family of hard satisfiable 3-SAT formulas corresponding to an ordered spin-glass model from statistical physics. This model has provably "glassy" b…