{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:42:39Z","timestamp":1777092159745,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316111","type":"print"},{"value":"9783642316128","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31612-8_25","type":"book-chapter","created":{"date-parts":[[2012,6,18]],"date-time":"2012-06-18T05:14:42Z","timestamp":1339996482000},"page":"327-340","source":"Crossref","is-referenced-by-count":2,"title":["Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas"],"prefix":"10.1007","author":[{"given":"Dimitris","family":"Achlioptas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ricardo","family":"Menchaca-Mendez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-2","key":"25_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D.: Lower bounds for random 3-sat via differential equations. Theoretical Computer Science\u00a0265(1-2), 159\u2013185 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.jcss.2003.07.011","volume":"68","author":"D. Achlioptas","year":"2004","unstructured":"Achlioptas, D., Beame, P., Molloy, M.: A sharp threshold in proof complexity yields lower bounds for satisfiability search. Journal of Computer and System Sciences\u00a068(2), 238\u2013268 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 793\u2013802. IEEE (2008)","DOI":"10.1109\/FOCS.2008.11"},{"issue":"1","key":"25_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(01)00154-2","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D., Kirousis, L.M., Kranakis, E., Krizanc, D.: Rigorous results for random (2+ p)-SAT. Theoretical Computer Science\u00a0265(1), 109\u2013129 (2001)","journal-title":"Theoretical Computer Science"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Menchaca-Mendez, R.: Unsatisfiability bounds for random csps from an energetic interpolation method (2012) (to appear in ICALP 2012)","DOI":"10.1007\/978-3-642-31594-7_1"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Tetali, P.: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. In: STOC 2010, pp. 105\u2013114 (2010)","DOI":"10.1145\/1806689.1806706"},{"key":"25_CR7","unstructured":"Beame, P., Pitassi, T.: Propositional proof complexity: Past, present and future. Current Trends in Theoretical Computer Science, 42\u201370 (2001)"},{"key":"25_CR8","first-page":"322","volume-title":"Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993","author":"A.Z. Broder","year":"1993","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-cnf formulas. In: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993, pp. 322\u2013330. Society for Industrial and Applied Mathematics, Philadelphia (1993), \nhttp:\/\/dl.acm.org\/citation.cfm?id=313559.313794"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Reed, B.: Mick gets some (the odds are on his side) [satisfiability]. In: Proceedings 33rd Annual Symposium on Foundations of Computer Science, pp. 620\u2013627. IEEE (1992)","DOI":"10.1109\/SFCS.1992.267789"},{"issue":"4","key":"25_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 Association for Computing Machinery\u00a035(4), 759\u2013768 (1988)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: On belief propagation guided decimation for random k-sat. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 957\u2013966. SIAM (2011)","DOI":"10.1137\/1.9781611973082.74"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Cook, S., Mitchell, D.: Finding hard instances of the satisfiability problem. In: Satisfiability Problem: Theory and Applications: DIMACS Workshop, March 11-13, vol.\u00a035, p. 1. Amer. Mathematical Society (1997)","DOI":"10.1090\/dimacs\/035\/01"},{"issue":"30-32","key":"25_CR13","doi-asserted-by":"publisher","first-page":"2920","DOI":"10.1016\/j.tcs.2009.02.020","volume":"410","author":"J. D\u00edaz","year":"2009","unstructured":"D\u00edaz, J., Kirousis, L., Mitsche, D., P\u00e9rez-Gim\u00e9nez, X.: On the satisfiability threshold of formulas with three literals per clause. Theoretical Computer Science\u00a0410(30-32), 2920\u20132934 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"25_CR14","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1023\/A:1022885828956","volume":"111","author":"S. Franz","year":"2003","unstructured":"Franz, S., Leone, M.: Replica bounds for optimization problems and diluted spin systems. Journal of Statistical Physics\u00a0111(3), 535\u2013564 (2003)","journal-title":"Journal of Statistical Physics"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1998","unstructured":"Friedgut, E.: Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc.\u00a012, 1017\u20131054 (1998)","journal-title":"J. Amer. Math. Soc."},{"issue":"2","key":"25_CR16","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. Frieze","year":"1996","unstructured":"Frieze, A., Suen, S.: Analysis of Two Simple Heuristics on a Random Instance ofk-sat. Journal of Algorithms\u00a020(2), 312\u2013355 (1996)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"25_CR17","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"Goerdt, A.: A threshold for unsatisfiability. Journal of Computer and System Sciences\u00a053(3), 469\u2013486 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"25_CR18","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00220-002-0699-y","volume":"230","author":"F. Guerra","year":"2002","unstructured":"Guerra, F., Toninelli, F.L.: The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics\u00a0230(1), 71\u201379 (2002)","journal-title":"Communications in Mathematical Physics"},{"issue":"4","key":"25_CR19","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A.C. Kaporis","year":"2006","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms\u00a028(4), 444\u2013480 (2006)","journal-title":"Random Structures & Algorithms"},{"issue":"19","key":"25_CR20","doi-asserted-by":"publisher","first-page":"197205","DOI":"10.1103\/PhysRevLett.94.197205","volume":"94","author":"M. M\u00e9zard","year":"2005","unstructured":"M\u00e9zard, M., Mora, T., Zecchina, R.: Clustering of solutions in the random satisfiability problem. Physical Review Letters\u00a094(19), 197205 (2005)","journal-title":"Physical Review Letters"},{"issue":"5582","key":"25_CR21","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M. M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science\u00a0297(5582), 812\u2013815 (2002)","journal-title":"Science"},{"issue":"3","key":"25_CR22","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"C. Ming-Te","year":"1990","unstructured":"Ming-Te, C., Franco, J.: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the <i> k<\/i> satisfiability problem. Information Sciences\u00a051(3), 289\u2013314 (1990)","journal-title":"Information Sciences"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","volume":"56","author":"R. Monasson","year":"1997","unstructured":"Monasson, R., Zecchina, R.: Statistical mechanics of the random k-satisfiability model. Phys. Rev. E\u00a056, 1357\u20131370 (1997), \nhttp:\/\/link.aps.org\/doi\/10.1103\/PhysRevE.56.1357","journal-title":"Phys. Rev. E"},{"issue":"3","key":"25_CR24","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00440-004-0342-2","volume":"130","author":"D. Panchenko","year":"2004","unstructured":"Panchenko, D., Talagrand, M.: Bounds for diluted mean-fields spin glass models. Probability Theory and Related Fields\u00a0130(3), 319\u2013336 (2004)","journal-title":"Probability Theory and Related Fields"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2014 SAT 2012"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31612-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:09:50Z","timestamp":1777090190000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-31612-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316111","9783642316128"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31612-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}