{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:45:35Z","timestamp":1725479135254},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540262763"},{"type":"electronic","value":"9783540316794"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11499107_41","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T17:56:25Z","timestamp":1279130185000},"page":"475-481","source":"Crossref","is-referenced-by-count":1,"title":["Threshold Behaviour of WalkSAT and Focused Metropolis Search on Random 3-Satisfiability"],"prefix":"10.1007","author":[{"given":"Sakari","family":"Seitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Alava","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pekka","family":"Orponen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"41_CR1","unstructured":"Aurell, E., Gordon, U., Kirkpatrick, S.: Comparing beliefs, surveys and random walks. In: NIPS 2004 (2004), arXiv.org: cond-mat\/0406217"},{"key":"41_CR2","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":"41_CR3","unstructured":"Braunstein, A., M\u00e9zard, M., Zecchina, R.: Survey propagation: an algorithm for satisfiability, arXiv.org:cs.CC\/0212002"},{"key":"41_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/jcph.1993.1010","volume":"104","author":"G. Dueck","year":"1993","unstructured":"Dueck, G.: New optimization heuristics: the great deluge algorithm and the record-to-record travel. J. Comput. Phys.\u00a0104, 86\u201392 (1993)","journal-title":"J. Comput. Phys."},{"key":"41_CR5","unstructured":"Hoos, H.H.: An adaptive noise mechanism for WalkSAT. In: AAAI 2002, pp. 655\u2013660 (2002)"},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0004-3702(99)00048-X","volume":"112","author":"H.H. Hoos","year":"1999","unstructured":"Hoos, H.H., St\u00fctzle, T.: Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif. Intell.\u00a0112, 213\u2013232 (1999)","journal-title":"Artif. Intell."},{"key":"41_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/11527695_16","volume-title":"Theory and Applications of Satisfiability Testing","author":"H. Jia","year":"2005","unstructured":"Jia, H., Moore, C., Selman, B.: From spin glasses to hard satisfiable formulas. In: Hoos, H.H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 199\u2013210. Springer, Heidelberg (2005)"},{"key":"41_CR8","unstructured":"McAllester, D., Selman, B., Kautz, H.: Evidence for invariants in local search. In: AAAI 1997, pp. 321\u2013326 (1997)"},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equations of state calculations by fast computing machines. J. Chem. Phys.\u00a021, 1087\u20131092 (1953)","journal-title":"J. Chem. Phys."},{"key":"41_CR10","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: AAAI 1992, pp. 459\u2013465 (1992)"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: On selecting a satisfying truth assignment. In: FOCS 1991, pp. 163\u2013169 (1991)","DOI":"10.1109\/SFCS.1991.185365"},{"key":"41_CR12","unstructured":"Parisi, G.: On local equilibrium equations for clustering states, arXiv.org:cs.CC\/0212047"},{"key":"41_CR13","unstructured":"Parkes, A.J.: Distributed local search, phase transitions, and polylog time. In: Proc. Workshop on Stochastic Search Algorithms, IJCAI 2001 (2001)"},{"key":"41_CR14","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, pp. 708\u2013713. Springer, Heidelberg (2002)"},{"key":"41_CR15","series-title":"Electronic Notes in Discrete Mathematics","volume-title":"Workshop on Typical Case Complexity and Phase Transitions, LICS 2003","author":"S. Seitz","year":"2003","unstructured":"Seitz, S., Orponen, P.: An efficient local search method for random 3-satisfiability. In: Workshop on Typical Case Complexity and Phase Transitions, LICS 2003. Electronic Notes in Discrete Mathematics, vol.\u00a016. Elsevier, Amsterdam (2003)"},{"key":"41_CR16","unstructured":"Seitz, S., Alava, M., Orponen, P.: Focused local search for random 3-satisfiability, arXiv.org:cond-mat\/0501707"},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. In: Cliques, Coloring, and Satisfiability. AMS DIMACS Series, vol.\u00a026, pp. 521\u2013532 (1996)","DOI":"10.1090\/dimacs\/026\/25"},{"key":"41_CR18","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":"41_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-540-24605-3_10","volume-title":"Theory and Applications of Satisfiability Testing","author":"G. Semerjian","year":"2004","unstructured":"Semerjian, G., Monasson, R.: A study of Pure Random Walk on random satisfiability problems with \u201cphysical\u201d methods. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 120\u2013134. Springer, Heidelberg (2004)"},{"key":"41_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-46135-3_15","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"W. Wei","year":"2002","unstructured":"Wei, W., Selman, B.: Accelerating random walks. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 216\u2013232. Springer, Heidelberg (2002)"}],"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\/11499107_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:41:21Z","timestamp":1619491281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11499107_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540262763","9783540316794"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11499107_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}