Correction on: A. Frieze and M. Molloy. The satisfiability threshold for randomly generated binary constraint satisfaction problems. Proceedings of RANDOM 2003.

The following papers also study the satisfiability threshold of some random CSP's whose domain size, m, grows with the number of variables, n. The third one (which predated ours) also establishes resolution complexity lower bounds for some such models. Thus we were wrong when we said that our reference [13] was the first study of the case where m grows with n, and when we said that our Theorem 2 is the first resolution complexity lower bound for such a model.

Barbara M Smith. "Constructing an Asymptotic Phase Transition in Random Binary Constraint Satisfaction Problems" Journal of Theoretical Computer Science vol. 265, pp. 265-283 (Special Issue on NP-Hardness and Phase Transitions), 2001. An earlier version is available online as School of Computing Research Report 2000.02, University of Leeds, January 2000.

Ke Xu and Wei Li. "Exact Phase Transitions in Random Constraint Satisfaction Problems." Journal of Artificial Intelligence Research, 12(2000):93-103.

K. Xu and W. Li. "Many hard examples in exact phase transitions with application to generating hard satisfiable instances." Technical Report cs.CC/0302001, Computing Research Repository (CoRR), 2003.