{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T16:59:14Z","timestamp":1790009954967,"version":"4.0.1"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Let $\\mathbf{\\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. We prove that the \\tt Walksat algorithm from Papadimitriou [On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163--169] and Sch\u00f6ning [A probabilistic algorithm for $k$-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410--414] finds a satisfying assignment of $\\mathbf{\\Phi}$ in polynomial time with high probability if $m\/n\\leq\\rho\\cdot2^k\/k$ for a certain constant $\\rho&gt;0$. This is an improvement by a factor of $\\Theta(k)$ over the best previous analysis of \\tt Walksat from Coja-Oghlan et al. [On smoothed $k$-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 451--460].<\/jats:p>","DOI":"10.1137\/12090191x","type":"journal-article","created":{"date-parts":[[2014,8,5]],"date-time":"2014-08-05T14:57:17Z","timestamp":1407250637000},"page":"1456-1485","source":"Crossref","is-referenced-by-count":11,"title":["Analyzing Walksat on Random Formulas"],"prefix":"10.1137","volume":"43","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,8,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00159-1"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703434231"},{"key":"atypb3","first-page":"947","volume":"17","author":"Achlioptas D.","year":"2004","journal-title":"J. AMS"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704440107"},{"key":"atypb5","first-page":"322","author":"Broder A. Z.","year":"1993","journal-title":"Philadelphia"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(90)90030-E"},{"key":"atypb7","first-page":"331","author":"Cheeseman P.","year":"1991","journal-title":"San Francisco"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e1tal and B. Reed,\n                      Mick gets some (the odds are on his side)\n                      , in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1992, pp. 620-627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/09076516X"},{"key":"atypb10","first-page":"451","author":"Coja-Oghlan A.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0016"},{"key":"atypb12","unstructured":"M. Hajiaghayi and G. Sorkin,\n                      The Satisfiability Threshold of Random 3-SAT Is at Least 3.52\n                      , IBM Research Report RC22942, 2003."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , John Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20104"},{"key":"atypb15","unstructured":"D. Mitchell, B. Selman, and H. Levesque,\n                      Hard and easy distribution of SAT problems\n                      , in Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92), American Association for Artificial Intelligence, Palo Alto, CA, 1992, pp. 459-465."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou,\n                      On selecting a satisfying truth assignment\n                      , in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163-169.","DOI":"10.1109\/SFCS.1991.185365"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning,\n                      A probabilistic algorithm for $k$-SAT and constraint satisfaction problems\n                      , in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410-414.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"B. Selman, H. Kautz, and B. Cohen,\n                      Local search strategies for satisfiability testing\n                      , in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, D. S. Johnson and M. A. Trick, eds., American Mathematical Society, Providence, RI, 1996, pp. 521-532.","DOI":"10.1090\/dimacs\/026\/25"},{"key":"atypb20","first-page":"120","volume":"2919","author":"Semerjian G.","year":"2003","journal-title":"Sci."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/12090191X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:21:19Z","timestamp":1787340079000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/12090191X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/12090191X"],"URL":"https:\/\/doi.org\/10.1137\/12090191x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}