{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T16:10:26Z","timestamp":1740327026917,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"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_10","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:50:35Z","timestamp":1280393435000},"page":"120-134","source":"Crossref","is-referenced-by-count":7,"title":["A Study of Pure Random Walk on Random Satisfiability Problems with \u201cPhysical\u201d Methods"],"prefix":"10.1007","author":[{"given":"Guilhem","family":"Semerjian","sequence":"first","affiliation":[]},{"given":"R\u00e9mi","family":"Monasson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning, U.: A Probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica\u00a032, 615\u2013623 (2002)","journal-title":"Algorithmica"},{"key":"10_CR2","unstructured":"Alekhnovich, M., Ben-Sasson, E.: Analysis of the Random Walk Algorithm on Random 3-CNFs (2002) (preprint)"},{"key":"10_CR3","unstructured":"Cocco, S., Montanari, A., Monasson, R., Semerjian, G.: Approximate analysis of search algorithms with \u201cphysical\u201d methods. cs.CC\/0302003"},{"key":"10_CR4","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and Easy Distributions of SAT Problems. In: Proc. of the Tenth Natl. Conf. on Artificial Intelligence (AAAI 1992), pp. 440\u2013446. The AAAI Press \/ MIT Press (1992)"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On Selecting a Satisfying Truth Assignment. In: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 163\u2013169 (1991)","DOI":"10.1109\/SFCS.1991.185365"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 192\u2013203. Springer, Heidelberg (2002)"},{"key":"10_CR7","unstructured":"Baumer, S., Schuler, R.: Improving a probabilistic 3-SAT algorithm by dynamic search and independant clause pairs (in this volume)"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1007\/3-540-46135-3_50","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"A.J. Parkes","year":"2002","unstructured":"Parkes, A.J.: Scaling Properties of Pure Random Walk on Random 3-SAT. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, p. 708. Springer, Heidelberg (2002)"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"66103","DOI":"10.1103\/PhysRevE.67.066103","volume":"67","author":"G. Semerjian","year":"2003","unstructured":"Semerjian, G., Monasson, R.: Relaxation and metastability in a local search procedure for the random satisfiability problem. Phys. Rev. E\u00a067, 066103 (2003)","journal-title":"Phys. Rev. E"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"66104","DOI":"10.1103\/PhysRevE.67.066104","volume":"67","author":"W. Barthel","year":"2003","unstructured":"Barthel, W., Hartmann, A.K., Weigt, M.: Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms. Phys. Rev. E\u00a067, 066104 (2003)","journal-title":"Phys. Rev. E"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1023\/A:1006350622830","volume":"24","author":"H.H. Hoos","year":"2000","unstructured":"Hoos, H.H., St\u00fctzle, T.: Local Search Algorithms for SAT: An Empirical Evaluation. J. Automated reasoning\u00a024, 421 (2000)","journal-title":"J. Automated reasoning"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"36115","DOI":"10.1103\/PhysRevE.64.036115","volume":"64","author":"G. Semerjian","year":"2001","unstructured":"Semerjian, G., Cugliandolo, L.F.: Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses. Phys. Rev. E\u00a064, 036115 (2001)","journal-title":"Phys. Rev. E"},{"key":"10_CR13","unstructured":"Cocco, S., Monasson, R.: Restarts and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland- Logemann algorithm. To appear in Annals of Mathematics and Artificial Intelligence (2003)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Dubois, O., Mandler, J.: The 3-XORSAT threshold. In: Proc. of the 43rd annual IEEE symposium on Foundations of Computer Science, Vancouver, pp. 769\u2013778 (2002)","DOI":"10.1109\/SFCS.2002.1182002"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"47205","DOI":"10.1103\/PhysRevLett.90.047205","volume":"90","author":"S. Cocco","year":"2003","unstructured":"Cocco, S., Dubois, O., Mandler, J., Monasson, R.: Rigorous decimation-based construction of ground pure states for spin glass models on random lattices. Phys. Rev. Lett.\u00a090, 047205 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1023\/A:1022886412117","volume":"111","author":"M. M\u00e9zard","year":"2003","unstructured":"M\u00e9zard, M., Ricci-Tersenghi, F., Zecchina, R.: Alternative solutions to diluted p-spin models and XORSAT problems. J. Stat. Phys.\u00a0111, 505 (2003)","journal-title":"J. Stat. Phys."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Peres, Y.: The Threshold for Random k-SAT is 2 k (ln 2 + o(1)) (2002) (preprint)","DOI":"10.1145\/780575.780577"},{"key":"10_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 (1997)","journal-title":"Phys. Rev. E"},{"key":"10_CR19","unstructured":"Selman, B., Kautz, H., Cohen, B.: Noise Strategies for Improving Local Search. In: Proc. AAAI 1994, Seattle, WA, pp. 337\u2013343 (1994)"},{"key":"10_CR20","unstructured":"McAllester, D., Selman, B., Kautz, H.: Evidence for Invariants in Local Search. In: Proc. AAAI 1997, Providence, RI (1997)"},{"key":"10_CR21","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S1571-0653(04)00463-9","volume":"16","author":"Sakari Seitz","year":"2003","unstructured":"Seitz, S., Orponen, P.: An efficient local search method for random 3-Satisfiability (2003) (preprint)","journal-title":"Electronic Notes in Discrete Mathematics"}],"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_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T15:29:58Z","timestamp":1740324598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24605-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208518","9783540246053"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24605-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}