{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:04:59Z","timestamp":1777125899854,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_1","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"1-12","source":"Crossref","is-referenced-by-count":2,"title":["Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method"],"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":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Achioptas, D., Sorkin, G.: Optimal myopic algorithms for random 3-sat. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science 2000, pp. 590\u2013600. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892327"},{"issue":"1-2","key":"1_CR2","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":"1_CR3","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":"1_CR4","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Coja-Oghlan, A.: Algorithmic barriers from phase transitions. In: 49th Annual IEEE Symp. on Foundations of Computer Science 2008, pp. 793\u2013802 (2008)","DOI":"10.1109\/FOCS.2008.11"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Menchaca-Mendez, R.: Exponential lower bounds for dpll algorithms on satisfiable random 3-cnf formulas (2012) (to appear in SAT 2012)","DOI":"10.1007\/978-3-642-31612-8_25"},{"key":"1_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"},{"issue":"4","key":"1_CR7","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":"1_CR8","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"},{"issue":"30-32","key":"1_CR9","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":"1_CR10","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":"1_CR11","doi-asserted-by":"publisher","first-page":"10967","DOI":"10.1088\/0305-4470\/36\/43\/021","volume":"36","author":"S. Franz","year":"2003","unstructured":"Franz, S., Leone, M., Toninelli, F.: Replica bounds for diluted non-poissonian spin systems. Journal of Physics A: Mathematical and General\u00a036, 10967 (2003)","journal-title":"Journal of Physics A: Mathematical and General"},{"issue":"1","key":"1_CR12","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.: 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":"1_CR13","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A. Kaporis","year":"2006","unstructured":"Kaporis, A., Kirousis, L., Lalas, E.: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms\u00a028(4), 444\u2013480 (2006)","journal-title":"Random Structures & Algorithms"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1002\/rsa.20090","volume":"28","author":"S. Mertens","year":"2006","unstructured":"Mertens, S., M\u00e9zard, M., Zecchina, R.: Threshold values of random k-sat from the cavity method. Random Structures & Algorithms\u00a028(3), 340\u2013373 (2006)","journal-title":"Random Structures & Algorithms"},{"key":"1_CR15","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, physics, and computation","author":"M. Mezard","year":"2009","unstructured":"Mezard, M., Montanari, A.: Information, physics, and computation. Oxford University Press, USA (2009)"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"9209","DOI":"10.1088\/0305-4470\/31\/46\/011","volume":"31","author":"R. Monasson","year":"1998","unstructured":"Monasson, R., Zecchina, R.: Tricritical points in random combinatorics: the-sat case. Journal of Physics A: Mathematical and General\u00a031, 9209 (1998)","journal-title":"Journal of Physics A: Mathematical and General"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"3881","DOI":"10.1103\/PhysRevLett.76.3881","volume":"76","author":"R. Monasson","year":"1996","unstructured":"Monasson, R., Zecchina, R.: Entropy of the K -satisfiability problem. Phys. Rev. Lett.\u00a076, 3881\u20133885 (1996), http:\/\/link.aps.org\/doi\/10.1103\/PhysRevLett.76.3881","journal-title":"Phys. Rev. Lett."},{"key":"1_CR18","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), http:\/\/link.aps.org\/doi\/10.1103\/PhysRevE.56.1357","journal-title":"Phys. Rev. E"},{"issue":"9","key":"1_CR19","doi-asserted-by":"publisher","first-page":"3221","DOI":"10.1109\/TIT.2005.853320","volume":"51","author":"A. Montanari","year":"2005","unstructured":"Montanari, A.: Tight bounds for ldpc and ldgm codes under map decoding. IEEE Transactions on Information Theory\u00a051(9), 3221\u20133246 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"1_CR20","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","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:12:07Z","timestamp":1743595927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}