I am an NSF Graduate Research Fellow (2004-2007)

I am a PhD student in computer science department of UNM, and doing research in NP-complete problems with Prof. Cris Moore

Here is some fun things I'm doing now:

The SAT problem, the problem of deciding whether a given boolean formula is satisfiable, is one of the well-known NP-complete problems. Although it is believed that the problem is not solvable in polynomial-time in the worst case, many heuristic algorithms have been proposed for the problem and some of them seem to be quite good on average. For testing the performance of these SAT solvers, it would be useful to have some solvable hard instances with a given solution. Here hard means that resolution of an instance takes a time exponential in N for any known algorithm. I did some research on how to construct some random hard instances with a given solution.

Here is my first paper in computer science: Dimitris Achloptas, haixia Jia and Cris Moore, Hiding Satisfying Assignments: Two are Better than One. Journal of Artificial Intelligence Research, to appear; Presented in AAAI 2004.

Another paper about hard instances: Haixia Jia, Cris Moore and Bart Selman, From a glass spin model to a 3-SAT hard formula. Presented in SAT 2004

Another paper about hard instances: Haixia Jia, Cris Moore and Doug Strain, Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively. Accepted by AAAI 2005.

More recently, I'm working on random graph coloring problem which is also a very common NP-complete problem. Cris and I analyze the behavior of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on random graphs in the ``easy'' regime, i.e. where the average degree is c least than 3.847. We exactly calculate the probability that DPLL finds a 3-coloring with no backtracking at all, by calculating the probability distribution of the number of 1-color vertices at a given point in the algorithm, and exactly analyzing the correlations between their colors. We also find that as we approach the transition from polynomial to exponential running time at c = 3.847 from below, that the probability of success without backtracking goes to zero faster than any analytic function, a so-called ``infinite-order phase transition'' in the language of statistical physics. Here is the paper: Haixia Jia and Cris Moore, How much backtracking does it take to color sparse random graphs? Rigorous results on heavy tails. CP 2004