{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T13:18:53Z","timestamp":1773667133547,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2001,10,1]],"date-time":"2001-10-01T00:00:00Z","timestamp":1001894400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,10,1]],"date-time":"2001-10-01T00:00:00Z","timestamp":1001894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2001,10]]},"DOI":"10.1023\/a:1011402324562","type":"journal-article","created":{"date-parts":[[2002,12,23]],"date-time":"2002-12-23T05:16:33Z","timestamp":1040620593000},"page":"329-344","source":"Crossref","is-referenced-by-count":47,"title":["Random Constraint Satisfaction: A More Accurate Picture"],"prefix":"10.1007","volume":"6","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael S. O.","family":"Molloy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lefteris M.","family":"Kirousis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannis C.","family":"Stamatiou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"351207_CR1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D. Achlioptas","year":"1999","unstructured":"Achlioptas, D., & Friedgut, E. (1999). A sharp threshold for k\u2013colorability. Random Structure and Algorithms 14: 13\u201370.","journal-title":"Random Structure and Algorithms"},{"key":"351207_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Kirousie, L. M., Kranakiz, E., Krizanc, D., Molloy, M. S. O., & Stamation, Y. C. (1997). Random constraint satisfaction: A more accurate picture. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP 97), pages 107\u2013120, Springer\u2013Verlag.","DOI":"10.1007\/BFb0017433"},{"key":"351207_CR3","doi-asserted-by":"crossref","first-page":"R29","DOI":"10.37236\/1461","volume":"6","author":"D. Achlioptas","year":"1999","unstructured":"Achlioptas, D., & Molloy, M. (1999). Almost all graphs with 2.522 n edges are not 3\u2013colorable. Electronic Journal of Combinatorics 6: R29.","journal-title":"Electronic Journal of Combinatorics"},{"key":"351207_CR4","volume-title":"The Probabilitstic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J. H., & Erdos, P. (1992). The Probabilitstic Method. New York: J. Wiley"},{"key":"351207_CR5","unstructured":"Bobrow, D. G., & Brady, M. eds., (1996). Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity. Guest editors: T. Hogg, B. A. Hubermann, & C. P. Williams, Artificial Intelligence 81, 1\u20132."},{"key":"351207_CR6","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1996","unstructured":"Bollob\u00e1s, B. (1996). Random Graphs. London: Academic Press."},{"key":"351207_CR7","unstructured":"Broder, A. Z. Frieze, A. M. & Uplas, E. (1993). In the satisfiability and maximum satisfiability of random 3\u2013CNF formulas. In Proceedings of the Fourth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pages 322\u2013330."},{"key":"351207_CR8","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M.\u2013T. Chao","year":"1986","unstructured":"Chao, M.\u2013T., & Franco, J. (1986). Probabilistic analysis of two heuristics for the 3\u2013satisfiability problem. SIAM Journal on Computing 15: 1106\u20131118.","journal-title":"SIAM Journal on Computing"},{"key":"351207_CR9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"M.\u2013T. Chao","year":"1990","unstructured":"Chao, M.\u2013T., & Franco, J. (1990). Probabilistic analysis of a generalization of the unit\u2013clause literal selection heuristic for the k\u2013satisfiability problem. Information Science 51: 289\u2013314.","journal-title":"Information Science"},{"key":"351207_CR10","unstructured":"Cheeseman, P., Kanfsky B., & Taylor, W. (1991). Where the really hard problems are. Proceedings of IJCAI 91, pages 331\u2013337."},{"key":"351207_CR11","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal V., & Reed, B. (1992). Mick gets some (the odds are on his side), In Proceedings of 33rd IEEE Symposium on Foundations of Computer Science, pages 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"351207_CR12","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"Dechter, R. (1992). Constraint networks, In S. Shapiro, ed., Encyclopedia of Artificial Intelligence, 2nd ed., pages 276\u2013285, New York: Wiley.","edition":"2nd ed."},{"key":"351207_CR13","unstructured":"Dubois, O., & Boufkhad, Y. (1996). A General Upper Bound for the Satisfiability Threshold of Random r\u2013SAT Formulae. Preprint, LAFORIA, CNRS\u2013Universit\u00e9 Paris 6."},{"key":"351207_CR14","first-page":"17","volume":"3","author":"P. Erdos","year":"1960","unstructured":"Erdos, P., & R\u00e9ny, A. (1960). On the evolution of random graphs. Publ. of the Math. Inst. of the Hung. Acad. Sci. 3: 17\u201361.","journal-title":"Publ. of the Math. Inst. of the Hung. Acad. Sci."},{"key":"351207_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300001590","volume":"4","author":"A. El Maftouhi","year":"1995","unstructured":"El Maftouhi, A., & Fernandez de la Vega, W. (1995). On random 3\u2013SAT. Combinatorics, Probability and Computing 4: 189\u2013195.","journal-title":"Combinatorics, Probability and Computing"},{"key":"351207_CR16","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E. (1999). Sharp thresholds for graph properties and the k\u2013sat problem, appendix by Jean Bourgain. Journal of the American Mathematical Society 12: 1017\u20131054.","journal-title":"Journal of the American Mathematical Society"},{"key":"351207_CR17","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. Frieze","year":"1996","unstructured":"Frieze, A., & Suen, S. (1996). Analysis of two simple heuristics on a random instance of k\u2013SAT. Journal of Algorithm 20: 312\u2013355.","journal-title":"Journal of Algorithm"},{"key":"351207_CR18","unstructured":"Gent, I. (1999). Personal communication."},{"key":"351207_CR19","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"Goerdt, A. (1996). A threshold for unsatisfiability. Journal of Computer and System Science 53: 469\u2013486.","journal-title":"Journal of Computer and System Science"},{"key":"351207_CR20","doi-asserted-by":"crossref","unstructured":"Hogg, T. Refining the phase transition in combinatorial search. In Brady, M. eds., (1996). Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity. Guest editors: T. Hogg, B. A. Hubermann, & C. P. Williams, Artificial Intelligence 81 [5], pages 127\u2013154.","DOI":"10.1016\/0004-3702(95)00050-X"},{"key":"351207_CR21","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., & Linial, N. (1988). The influence of variables on Boolean functions. Proceedings of the 29th Annual Symposium on the Foundations of Computer Science, pages 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"351207_CR22","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"A. Kamath","year":"1995","unstructured":"Kamath, A., Motwani, R., Palem, K., & Spirakis, P. (1995). Tail bounds for occupancy and the satisfiability threshold conjecture. Random Structures and Algorithms 7: 59\u201380.","journal-title":"Random Structures and Algorithms"},{"key":"351207_CR23","unstructured":"Xu, K. (1999). Personal communication."},{"key":"351207_CR24","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., & Selman, B. (1994). Critical behavior in the satisfiability of random Boolean expression Science 264: 1297\u20131301.","journal-title":"Science"},{"key":"351207_CR25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"L. M. Kirousis","year":"1998","unstructured":"Kirousis, L. M., Kranakis, E., Krizanc, D., & Stamatiou, Y. C. (1998). Approximating the unsatisfiability threshold of random formulas. Random Structures and Algorithms 12: 253\u2013269.","journal-title":"Random Structures and Algorithms"},{"key":"351207_CR26","doi-asserted-by":"crossref","unstructured":"Maclntyre, E., Prosser, P., Smith, B., & Walsh, T. (1998). Random constraint satisfaction: theory meets practice. In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP' 98).","DOI":"10.1007\/3-540-49481-2_24"},{"key":"351207_CR27","first-page":"285","volume-title":"Encyclopedia of Artificial Intelligence","author":"A. K. Mackworth","year":"1992","unstructured":"Mackworth, A. K. (1992). Constraint satisfaction. In S. Shapiro, ed., Encyclopedia of Artificial Intelligence. 2nd ed., pages 285\u2013293, New York: Wiley.","edition":"2nd ed."},{"key":"351207_CR28","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1017\/S096354830000016X","volume":"1","author":"C. McDiarmid","year":"1992","unstructured":"McDiarmid, C. (1992). On a correlation inequality of Farr. Combinatorics, Probability and Computing 1: 157\u2013160.","journal-title":"Combinatorics, Probability and Computing"},{"key":"351207_CR29","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(95)00049-6","volume":"81","author":"D. Mitchell","year":"1996","unstructured":"Mitchell, D., Selman, B., & Levesque, H. (1996). Generating hard satisfiability problems. Artificial Intelligence 81: 17\u201329.","journal-title":"Artificial Intelligence"},{"key":"351207_CR30","doi-asserted-by":"crossref","unstructured":"Prosser, P. An empirical study of phase transitions in binary constraint satisfaction problems. In Brady, M. eds., (1996). Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity. Guest editors: T. Hogg, B. A. Hubermann, & C. P. Williams, Artificial Intelligence 81 [5], 81\u2013109.","DOI":"10.1016\/0004-3702(95)00048-8"},{"key":"351207_CR31","doi-asserted-by":"crossref","unstructured":"Smith, B. M., & Dyer, M. E. Locating the phase transition in binary constraint satisfaction problems. In Brady, M. eds., (1996). Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity. Guest editors: T. Hogg, B. A. Hubermann, & C. P. Williams, Artificial Intelligence 81 [5], 155\u2013181.","DOI":"10.1016\/0004-3702(95)00052-6"},{"key":"351207_CR32","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970074","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. H. Spencer","year":"1994","unstructured":"Spencer, J. H. (1994). Ten Lectures on the Probabilistic Method, 2nd edition, Philadelphia: SIAM.","edition":"2nd edition"},{"key":"351207_CR33","first-page":"19","volume-title":"The Psychology of Computer Vision","author":"D. Waltz","year":"1995","unstructured":"Waltz, D. (1995). Understanding line drawings of scenes with shadows. The Psychology of Computer Vision, pages 19\u201391, New York: McGraw\u2013Hill"},{"key":"351207_CR34","unstructured":"Williams, C., & Hogg, T. (1992). Using deep structure to locate hard problems, Proceedings of AAAI\u201398, pages 472\u2013477."},{"key":"351207_CR35","unstructured":"Williams, C., & Hogg, T. Extending deep structure, (1993). Proceedings of AAAI\u201393, pages 152\u2013158."},{"key":"351207_CR36","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C. Williams","year":"1994","unstructured":"Williams, C., & Hogg, T. (1994). Exploiting the deep structure of constraint problems, Artificial Intelligence 70: 73\u2013117.","journal-title":"Artificial Intelligence"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011402324562.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1011402324562\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1011402324562.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:04:22Z","timestamp":1752379462000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1011402324562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,10]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,10]]}},"alternative-id":["351207"],"URL":"https:\/\/doi.org\/10.1023\/a:1011402324562","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,10]]}}}