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.