• B. Selman, D.G. Mitchell, and H.J. Levesque. Generating hard satisfiability problems, AIJ 81 (1996) 1-2, 17-30. [PS]
• J.M. Crawford and L.D. Auton. Experimental Results on the Crossover Point in Random 3SAT, AIJ 81 (1996) 1-2, 31-57. [PS]
• David G. Mitchell and Hector J. Levesque. Some Pitfalls for Experimenters with Random SAT, AIJ 81 (1996) 1-2, 111-125. [PS]
• T. Hogg. Refining the Phase Transition in Combinatorial Search, AIJ 81 (1996) 1-2, 127-154. [Link]
• J. W. Freeman. Hard Random 3-SAT Problems and the Davis-Putnam Procedure, AIJ 81 (1996) 1-2, 183-198.
• R. Schrag and J. M. Crawford, Implicates and Prime Implicates in Random 3SAT, AIJ 81 (1996) 1-2, 199-222. [PS]
• W. Zhang and R. E. Korf. A Study of Complexity Transitions on the Asymmetric Traveling Salesman Problem, AIJ 81 (1996) 1-2, 223-239.
• T. Bylander. A Probabilistic Analysis of Propositional STRIPS Planning, AIJ 81 (1996) 1-2, 241-271. [PS.GZ]
• J. C. Pemberton and W. Zhang. Epsilon-Transformation: Exploiting Phase Transitions to Solve Combinatorial Optimization Problems, AIJ 81 (1996) 1-2, 297-325.
• Scott H. Clearwater and Tad Hogg. Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms, AIJ 81 (1996) 1-2, 327-347. [Link]
• Carla Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems, Journal of Automated Reasoning, Vol. 24(1/2), pages 67-100, 2000. [PDF]
• Remi Monasson, Ricardo Zecchina, Scott Kirkpatrick, Bart Selman and Lidror Troyansky. Determining computational complexity from characteristic 'phase transitions'. Nature 400 (1999) 6740, 133-137. [PDF])