Hiding Satisfying Assignments: Two are Better than One (2005)
Achlioptas, Dimitris, Jia, Haixia, Moore, Cristopher
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-SAT formulas whose...
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively (2005)
Jia, Haixia, Moore, Cristopher, Strain, Doug
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 to choose a random...
How much backtracking does it take to color random graphs? Rigorous results on heavy tails (2004)
Jia, Haixia, Moore, Cristopher
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 of the...
From spin glasses to hard satisfiable formulas (2004)
Jia, Haixia, Moore, Cristopher, Selman, Bart
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'' behavior; that is,...