{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:35:36Z","timestamp":1725561336916},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208518"},{"type":"electronic","value":"9783540246053"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24605-3_16","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T04:50:35Z","timestamp":1280379035000},"page":"203-213","source":"Crossref","is-referenced-by-count":4,"title":["On the Probabilistic Approach to the Random Satisfiability Problem"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Parisi","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M. M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Science 297, 812 (2002)","journal-title":"Science"},{"key":"16_CR2","unstructured":"M\u00e9zard, M., Zecchina, R.: The random K-satisfiability problem: from an analytic solution to an efficient algorithm cond-mat 0207194"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Mitchell, D.G.: Finding Hard Instances of the Satisfiability Problem: A Survey. In: Du, Gu, Pardalos (eds.) Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a035 (1997)","DOI":"10.1090\/dimacs\/035\/01"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S. Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical Behaviour in the satisfiability of random Boolean expressions. Science\u00a0264, 1297 (1994)","journal-title":"Science"},{"key":"16_CR5","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s100510051065","volume":"14","author":"G. Biroli","year":"2000","unstructured":"Biroli, G., Monasson, R., Weigt, M.: A Variational description of the ground state structure in random satisfiability problems. Euro. Phys. J.\u00a0 B14, 551 (2000)","journal-title":"Euro. Phys. J."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Dubois, O., Monasson, R., Selman, B., Zecchina, R. (eds.) Phase Transitions in Combinatorial Problems. Theoret. Comp. Sci. 265 (2001), Biroli, G., Cocco, S., Monasson, R.: Physica A 306, 381 (2002)","DOI":"10.1016\/S0304-3975(01)00133-5"},{"key":"16_CR7","volume-title":"Spin Glass Theory and Beyond","author":"M. M\u00e9zard","year":"1987","unstructured":"M\u00e9zard, M., Parisi, G., Virasoro, M.A.: Spin Glass Theory and Beyond. World Scientific, Singapore (1987)"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1080\/14786437708235992","volume":"35","author":"D.J. Thouless","year":"1977","unstructured":"Thouless, D.J., Anderson, P.A., Palmer, R.G.: Solution of a \u2018solvable\u2019 model. Phil. Mag.\u00a035, 593 (1977)","journal-title":"Phil. Mag."},{"key":"16_CR9","first-page":"689","volume-title":"Advances in Neural Information Processing Systems 13","author":"J.S. Yedidia","year":"2001","unstructured":"Yedidia, J.S., Freeman, W.T., Weiss, Y.: Generalized Belief Propagation. In: Leen, T.K., Dietterich, T.G., Tresp, V. (eds.) Advances in Neural Information Processing Systems 13, pp. 689\u2013695. MIT Press, Cambridge (2001)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"F.R. Kschischang","year":"2002","unstructured":"Kschischang, F.R., Frey, B.J., Loeliger, H.-A.: Factor Graphs and the Sum-Product Algorithm. IEEE Trans. Infor. Theory\u00a047, 498 (2002)","journal-title":"IEEE Trans. Infor. Theory"},{"key":"16_CR11","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)","journal-title":"Phys. Rev. Lett."},{"key":"16_CR12","doi-asserted-by":"crossref","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R. Mulet","year":"2002","unstructured":"Mulet, R., Pagnani, A., Weigt, M., Zecchina, R.: Phys. Rev. Lett. 89, 268701 (2002)","journal-title":"Phys. Rev. Lett."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1088\/0305-4470\/22\/16\/003","volume":"22","author":"C. Dominicis De","year":"1989","unstructured":"De Dominicis, C., Goldschmidt, Y.Y.: Replica symmetry breaking in finite connectivity systems: a large connectivity expansion at finite and zero temperature. J. Phys. A. Math. Gen.\u00a022, 775 (1989)","journal-title":"J. Phys. A. Math. Gen."},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/PL00011099","volume":"20","author":"M. M\u00e9zard","year":"2001","unstructured":"M\u00e9zard, M., Parisi, G.: Eur. Phys. J. B 20, 217 (2001)","journal-title":"Eur. Phys. J. B"},{"key":"16_CR15","unstructured":"M\u00e9zard, M., Parisi, G.: The cavity method at zero temperature. condmat\/ 0207121 (2002) (to appear in J. Stat. Phys.)"},{"key":"16_CR16","unstructured":"Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-SAT formulae and the satisfiability threshold. In: Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, San Francisco, CA, vol. 124 (2000)"},{"key":"16_CR17","unstructured":"Franz, S., Leone, M.: Replica bounds for optimization problems and diluted spin systems, cond-mat\/0208280"},{"key":"16_CR18","unstructured":"Parisi, G.: Glasses, replicas and all that cond-mat\/0301157 (2003)"},{"key":"16_CR19","doi-asserted-by":"crossref","first-page":"047205","DOI":"10.1103\/PhysRevLett.90.047205","volume":"90","author":"S. Cocco","year":"2003","unstructured":"Cocco, S., Dubois, O., Mandler, J., Monasson, R.: Phys. Rev. Lett. 90, 047205 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"16_CR20","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s004400050009","volume":"117","author":"M. Talagrand","year":"2000","unstructured":"Talagrand, M.: Rigorous low temperature results for the p-spin mean field spin glass model. Prob. Theory and Related Fields 117, 303\u2013360 (2000)","journal-title":"Prob. Theory and Related Fields"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Dubois, O., Mandler, J.: In: FOCS 2002, 769 (2002)","DOI":"10.1016\/S0338-9898(02)80298-0"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/rsa.1015","volume":"18","author":"D. Aldous","year":"2001","unstructured":"Aldous, D.: The zeta(2) Limit in the Random Assignment Problem. Random Structures and Algorithms\u00a018, 381\u2013418 (2001)","journal-title":"Random Structures and Algorithms"},{"key":"16_CR23","unstructured":"Parisi, G.: cs.CC\/0212047 On local equilibrium equations for clustering states (2002)"},{"key":"16_CR24","unstructured":"Parisi, G.: cs.CC\/0212009 On the survey-propagation equations for the random Ksatisfiability problem (2002)"},{"key":"16_CR25","unstructured":"Braustein, A., Mezard, M., Weigt, M., Zecchina, R.: cond-mat\/0212451 Constraint Satisfaction by Survey Propagation (2002)"},{"key":"16_CR26","unstructured":"Braunstein, A., Mezard, M., Zecchina, R.: cs.CC\/0212002 Survey propagation: an algorithm for satisfiability (2002)"},{"key":"16_CR27","unstructured":"Parisi, G.: cs.CC\/0301015 Some remarks on the survey decimation algorithm for K-satisfiability (2003)"},{"key":"16_CR28","unstructured":"Talagrand, M.: private communication (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24605-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:54:18Z","timestamp":1559332458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24605-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208518","9783540246053"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24605-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}