{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T05:46:49Z","timestamp":1740894409689,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407706"},{"type":"electronic","value":"9783540451983"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_24","type":"book-chapter","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T03:32:30Z","timestamp":1294457550000},"page":"275-289","source":"Crossref","is-referenced-by-count":3,"title":["The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Molloy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Beame, P., Molloy, M.: A sharp threshold in proof complexity. In: Proceedings of STOC, pp. 337\u2013346 (2001)","DOI":"10.1145\/380752.380820"},{"key":"24_CR2","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1023\/A:1011402324562","volume":"6","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., Stamatiou, Y.: Random constraint satisfaction: a more accurate picture. Constraints\u00a06, 324\u2013329 (2001); Conference version in Proceedings of CP 1997, 107\u2013120","journal-title":"Constraints"},{"key":"24_CR3","unstructured":"Beame, P., Culberson, J., Mitchell, D.: The resolution complexity of random graph k-colourability (in preparation)"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Beame, P., Pitassi, T.: Simplified and improved resolution lower bounds. In: Proceedings of FOCS, pp. 274\u2013282 (1996)","DOI":"10.1109\/SFCS.1996.548486"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Beame, P., Karp, R., Pitassi, T., Saks, M.: The efficiency of resolution and Davis- Putnam procedures. In: Proceedings of STOC 1998 and SIAM Journal on Computing, vol.\u00a031, pp. 1048\u20131075 (2002)","DOI":"10.1137\/S0097539700369156"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow - resolution made simple. In: Proceedings of STOC 1999 and Journal of the ACM, vol.\u00a048 (2001)","DOI":"10.1145\/375827.375835"},{"key":"24_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"24_CR8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollob\u00e1s","year":"1980","unstructured":"Bollob\u00e1s, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal on Combinatorics\u00a01, 311\u2013316 (1980)","journal-title":"European Journal on Combinatorics"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","volume":"24","author":"E.A. Bender","year":"1978","unstructured":"Bender, E.A., Canfield, E.R.: The asymptotic number of labelled graphs with given degree sequence. Journal of Combinatorial Theory (A)\u00a024, 296\u2013307 (1978)","journal-title":"Journal of Combinatorial Theory (A)"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chvatal","year":"1988","unstructured":"Chvatal, V., Szemeredi, E.: Many hard examples for resolution. Journal of the ACM\u00a035, 759\u2013768 (1988)","journal-title":"Journal of the ACM"},{"key":"24_CR11","unstructured":"Creignou, N., Daude, H.: Random generalized satisfiability problems. In: Proceedings of SAT (2002)"},{"key":"24_CR12","first-page":"276","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"Dechter, R.: Constraint networks. In: Shapiro, S. (ed.) Encyclopedia of Artificial Intelligence, 2nd edn., pp. 276\u2013285. Wiley, New York (1992)","edition":"2"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1016\/S0304-3975(02)00317-1","volume":"290","author":"M. Dyer","year":"2003","unstructured":"Dyer, M., Frieze, A., Molloy, M.: A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theoretical Computer Scince\u00a0290, 1815\u20131828 (2003)","journal-title":"Theoretical Computer Scince"},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E.C. Freuder","year":"1982","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-free search. Journal of the ACM\u00a029, 24\u201332 (1982)","journal-title":"Journal of the ACM"},{"key":"24_CR15","unstructured":"Bobrow, D.G., Brady, M. (eds.): Special Volume on Frontiers in Problem Solving: Phase Transitions and Complexity; Hogg, T., Hubermann, B.A., Williams, C.( Guest eds.): Artificial Intelligence 81(1-2) (1996)"},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1023\/A:1011454308633","volume":"6","author":"I. Gent","year":"2001","unstructured":"Gent, I., MacIntyre, E., Prosser, P., Smith, B., Walsh, T.: Random constraint satisfaction: flaws and structure. Constraints\u00a06, 345\u2013372 (2001)","journal-title":"Constraints"},{"key":"24_CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley, Chichester (2000)"},{"key":"24_CR18","first-page":"285","volume-title":"Encyclopedia of Artificial Intelligence","author":"A.K. Mackworth","year":"1992","unstructured":"Mackworth, A.K.: Constraint satisfaction. In: Shapiro, S. (ed.) Encyclopedia of Artificial Intelligence, 2nd edn., pp. 285\u2013293. Wiley, New York (1992)","edition":"2"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Mitchell, D.: The Resolution complexity of random constraints. In: Van Hentenryck, P. (ed.) CP (2002)","DOI":"10.1007\/3-540-46135-3_20"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Mitchell, D.: The Resolution Complexity of Constraint Satisfaction. Ph.D. Thesis, University of Toronto (2002)","DOI":"10.1007\/3-540-46135-3_20"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Molloy, M.: Models for Random Constraint Satisfaction Problems. In: Proceedings of STOC 2002, pp. 209\u2013217 (2002); Longer version to appear in SIAM J. Computing","DOI":"10.1145\/509939.509941"},{"key":"24_CR22","unstructured":"Molloy, M.: When does the giant component bring unsatisfiability? (submitted)"},{"key":"24_CR23","unstructured":"Molloy, M., Salavatipour, M.: The resolution complexity of random constraint satisfaction problems (submitted)"},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jctb.1996.0036","volume":"67","author":"B. Pittel","year":"1996","unstructured":"Pittel, B., Spencer, J., Wormald, N.: Sudden emergence of a giant k-core in a random graph. Journal of Combinatorial Theory (B)\u00a067, 111\u2013151 (1996)","journal-title":"Journal of Combinatorial Theory (B)"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF02699376","volume":"81","author":"M. Talagrand","year":"1995","unstructured":"Talagrand, M.: Concentration of mesure and isoperimetric inequalities. Inst. Hautes \u00c9tudes Sci. Publ. Math.\u00a081, 73\u2013205 (1995)","journal-title":"Inst. Hautes \u00c9tudes Sci. Publ. Math."},{"key":"24_CR26","first-page":"19","volume-title":"The Psychology of Computer Vision","author":"D. Waltz","year":"1975","unstructured":"Waltz, D.: Understanding line drawings of scenes with shadows. In: Waltz, D. (ed.) The Psychology of Computer Vision, pp. 19\u201391. McGraw-Hill, New York (1975)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T14:52:29Z","timestamp":1740840749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}