{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T13:18:50Z","timestamp":1773667130284,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540637530","type":"print"},{"value":"9783540696421","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0017433","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:22:46Z","timestamp":1132644166000},"page":"107-120","source":"Crossref","is-referenced-by-count":40,"title":["Random constraint satisfaction: A more accurate picture"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lefteris M.","family":"Kirousis","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"}]},{"given":"Michael S. O.","family":"Molloy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannis C.","family":"Stamatiou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"9_CR1","unstructured":"D. Achlioptas and M. Molloy, \u201cAlmost all graphs with 2.522 n edges are not 3-colorable,\u201d Manuscript, University of Toronto."},{"key":"9_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J.H. Spencer, and P. Erd\u00f6s, The Probabilistic Method, J. Wiley, New York (1992)."},{"key":"9_CR3","unstructured":"D.G. Bobrow and M. Brady, eds., Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity, Guest editors: T. Hogg, B.A. Hubermann, and C.P. Williams, Artificial Intelligence, Vol. 81, Numbers 1\u20132 (1996)."},{"key":"9_CR4","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s, Random Graphs, Academic Press, London (1985)."},{"key":"9_CR5","unstructured":"A.Z. Broder, A.M. Frieze, and E. Upfal, \u201cOn the satisfiability and maximum satisfiability of random 3-CNF formulas,\u201d Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993) 322\u2010330."},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M.-T. Chao","year":"1986","unstructured":"M.-T. Chao and J. Franco, \u201cProbabilistic analysis of two heuristics for the 3-satisfiability problem,\u201d SIAM Journal on Computing, Vol. 15 (1986) 1106\u20131118.","journal-title":"SIAM Journal on Computing"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"M.-T. Chao","year":"1990","unstructured":"M.-T. Chao and J. Franco, \u201cProbabilistic analysis of a generalization of the unitclause literal selection heuristic for the k-satisfiability problem,\u201d Information Science, Vol. 51 (1990) 289\u2013314.","journal-title":"Information Science"},{"key":"9_CR8","unstructured":"P. Cheeseman, B. Kanefsky and W. Taylor, \u201cWhere the really hard problems are,\u201d Proceedings of IJCAI '91 (1991) 331\u2013337."},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal and B. Reed, \u201cMick gets some (the odds are on his side),\u201d in Proceedings of 33rd IEEE Symposium on Foundations of Computer Science (1992) 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"9_CR10","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"R. Dechter, \u201cConstraint networks,\u201d in S. Shapiro (ed.), Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 276\u2013285.","edition":"2nd ed."},{"key":"9_CR11","unstructured":"O. Dubois and Y. Boufkhad, A General Upper Bound for the Satisfiability Threshold of Random r-SAT Formulae, Preprint, LAFORIA, CNRS-Universit\u00e9 Paris 6, 1996."},{"key":"9_CR12","first-page":"17","volume":"5","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi, \u201cOn the evolution of random graphs,\u201d Publ. of the Math. Inst. of the Hung. Acad. Sci., Vol. 5 (1960) 17\u201361.","journal-title":"Publ. of the Math. Inst. of the Hung. Acad. Sci."},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300001590","volume":"4","author":"A. Maftouhi El","year":"1995","unstructured":"A. El Maftouhi and W. Fernandez de la Vega, \u201cOn random 3-SAT\u201d, Combinatorics, Probability and Computing, Vol. 4 (1995) 189\u2013195.","journal-title":"Combinatorics, Probability and Computing"},{"key":"9_CR14","unstructured":"E. Friedgut, \u201cSharp thresholds for graph properties and the k-sat problem,\u201d Manuscript in preparation."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. Frieze","year":"1996","unstructured":"A. Frieze and S. Suen, \u201cAnalysis of two simple heuristics on a random instance of k-SAT,\u201d Journal of Algorithms, Vol. 20 (1996) 312\u2013355.","journal-title":"Journal of Algorithms"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"A. Goerdt, \u201cA threshold for satisfiability,\u201d in I.M. Haven and V. Koubek (eds.) Proceedings of the Symposium on the Mathematical Foundations of Computer Science (1992) 264\u2013274.","DOI":"10.1007\/3-540-55808-X_25"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"T. Hogg, \u201cRefining the phase transition in combinatorial search,\u201d in [3], 127\u2013154.","DOI":"10.1016\/0004-3702(95)00050-X"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and N. Linial, \u201cThe influence of variables on Boolean functions\u201d, Proceedings of the 29th Annual Symposium on the Foundations of Computer Science (1988) 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"9_CR19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"A. Kamath","year":"1995","unstructured":"A. Kamath, R. Motwani, K. Palem, and P. Spirakis, \u201cTail bounds for occupancy and the satisfiability threshold conjecture,\u201d Random Structures and Algorithms, Vol. 7 (1995) 59\u201380.","journal-title":"Random Structures and Algorithms"},{"key":"9_CR20","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"S. Kirkpatrick and B. Selman, \u201cCritical behavior in the satisfiability of random Boolean expressions,\u201d Science 264, pp 1297\u20131301, 1994.","journal-title":"Science"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"L. M. Kirousis, E. Kranakis, and D. Krizanc, \u201cApproximating the unsatisfiability threshold of random formulas,\u201d Proceedings of the Fourth Annual European Symposium on Algorithms, ESA '96, (1996) 27\u201338.","DOI":"10.1007\/3-540-61680-2_44"},{"key":"9_CR22","first-page":"285","volume-title":"Encyclopedia of Artificial Intelligence","author":"A.K. Mackworth","year":"1992","unstructured":"A.K. Mackworth, \u201cConstraint satisfaction,\u201d in S. Shapiro (ed.) Encyclopedia of Artificial Intelligence, Wiley, New York, 2nd ed. (1992) 285\u2013293.","edition":"2nd ed."},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1017\/S096354830000016X","volume":"1","author":"C. McDiarmid","year":"1992","unstructured":"C. McDiarmid, \u201cOn a correlation inequality of Farr,\u201d Combinatorics, Probability and Computing, Vol. 1 (1992) 157\u2013160.","journal-title":"Combinatorics, Probability and Computing"},{"key":"9_CR24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(95)00049-6","volume":"81","author":"D. Mitchell","year":"1996","unstructured":"D. Mitchell, B. Selman, and H. Levesque, Generating hard satisfaability problems, Artificial Intelligence, Vol. 81 (1996), 17\u201329.","journal-title":"Artificial Intelligence"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"P. Prosser, \u201cAn empirical study of phase transitions in binary constraint satisfaction problems,\u201d in [3], 81\u2013109.","DOI":"10.1016\/0004-3702(95)00048-8"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"B.M. Smith and M.E. Dyer, \u201cLocating the phase transition in binary constraint satisfaction problems,\u201d in [3], 155\u2013181.","DOI":"10.1016\/0004-3702(95)00052-6"},{"key":"9_CR27","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970074","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. H. Spencer","year":"1994","unstructured":"J. H. Spencer, Ten Lectures on the Probabilistic Method, 2nd edition, SIAM, Philadelphia (1994).","edition":"2nd edition"},{"key":"9_CR28","first-page":"19","volume-title":"The Psychology of Computer Vision","author":"D. Waltz","year":"1975","unstructured":"D. Waltz, \u201cUnderstanding line drawings of scenes with shadows,\u201d The Psychology of Computer Vision, McGraw-Hill, New York (1975) 19\u201391."},{"key":"9_CR29","unstructured":"C. Williams and T. Hogg, \u201cUsing deep structure to locate hard problems,\u201d Proceedings of AAAI-92 (1992) 472\u2013477."},{"key":"9_CR30","unstructured":"C. Williams and T. Hogg, \u201cExtending deep structure,\u201d Proceedings of AAAI-93, (1993) 152\u2013158."},{"key":"9_CR31","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0004-3702(94)90104-X","volume":"70","author":"C. Williams","year":"1994","unstructured":"C. Williams and T. Hogg, \u201cExploiting the deep structure of constraint problems,\u201d Artificial Intelligence, Vol. 70 (1994) 73\u2013117.","journal-title":"Artificial Intelligence"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming-CP97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:53:25Z","timestamp":1586573605000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637530","9783540696421"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/bfb0017433","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}