{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T21:13:21Z","timestamp":1774646001163,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,1,20]],"date-time":"2017-01-20T00:00:00Z","timestamp":1484870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/G039070\/2"],"award-info":[{"award-number":["EP\/G039070\/2"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,2,9]]},"abstract":"\n Let \u03a6 be a uniformly distributed random\n k<\/jats:italic>\n -SAT formula with\n n<\/jats:italic>\n variables and\n m<\/jats:italic>\n clauses. Nonconstructive arguments show that \u03a6 is satisfiable for clause\/variable ratios\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n \u2a7d\n r<\/jats:italic>\n \n k<\/jats:italic>\n \u2212 SAT\n <\/jats:sub>\n \u223c 2\n k<\/jats:sup>\n ln 2 with high probability. Yet no efficient algorithm is known to find a satisfying assignment beyond\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n \u223c 2\n \n k<\/jats:italic>\n <\/jats:sup>\n ln (\n k<\/jats:italic>\n )\/\n k<\/jats:italic>\n with a nonvanishing probability. On the basis of deep but nonrigorous statistical mechanics ideas, a message passing algorithm called\n Belief Propagation Guided Decimation<\/jats:italic>\n has been put forward (M\u00e9zard, Parisi, Zecchina: Science 2002; Braunstein, M\u00e9zard, Zecchina: Random Struc. Algorithm 2005). Experiments suggested that the algorithm might succeed for densities very close to\n r<\/jats:italic>\n \n k<\/jats:italic>\n \u2212 SAT\n <\/jats:sub>\n for\n k<\/jats:italic>\n = 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of this algorithm on a nontrivial input distribution, in the present article we show that Belief Propagation Guided Decimation fails to solve random\n k<\/jats:italic>\n -SAT formulas already for\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n =\n O<\/jats:italic>\n (2\n \n k<\/jats:italic>\n <\/jats:sup>\n \/\n k<\/jats:italic>\n ), almost a factor of\n k<\/jats:italic>\n below the satisfiability threshold\n r<\/jats:italic>\n \n k<\/jats:italic>\n \u2212 SAT\n <\/jats:sub>\n . Indeed, the proof refutes a key hypothesis on which Belief Propagation Guided Decimation hinges for such\n m<\/jats:italic>\n \/\n n<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3005398","type":"journal-article","created":{"date-parts":[[2017,1,20]],"date-time":"2017-01-20T14:05:40Z","timestamp":1484921140000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Belief Propagation Guided Decimation Fails on Random Formulas"],"prefix":"10.1145","volume":"63","author":[{"given":"Amin","family":"Coja-Oghlan","sequence":"first","affiliation":[{"name":"Goethe University, Mathematics Institute, Frankfurt, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,1,20]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"947","article-title":"The threshold for random k-SAT is 2kln 2 − O(k)","volume":"17","author":"Achlioptas D.","year":"2004","unstructured":"D. Achlioptas and Y. Peres . 2004 . The threshold for random k-SAT is 2kln 2 − O(k) . Journal of the AMS 17 (2004), 947 -- 973 . D. Achlioptas and Y. Peres. 2004. The threshold for random k-SAT is 2kln 2 − O(k). Journal of the AMS 17 (2004), 947--973.","journal-title":"Journal of the AMS"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03602"},{"key":"e_1_2_1_3_1","volume-title":"Handbook of Satisfiability","author":"Achlioptas D.","unstructured":"D. Achlioptas . 2009. Handbook of Satisfiability . IOS Press , 245--270. D. Achlioptas. 2009. Handbook of Satisfiability. IOS Press, 245--270."},{"key":"e_1_2_1_4_1","volume-title":"Proc. 41st FOCS","author":"Achlioptas D.","year":"2000","unstructured":"D. Achlioptas and G. Sorkin . 2000. Optimal myopic algorithms for random 3-SAT . Proc. 41st FOCS ( 2000 ), 590--600. D. Achlioptas and G. Sorkin. 2000. Optimal myopic algorithms for random 3-SAT. Proc. 41st FOCS (2000), 590--600."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.915695"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1935.0122"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20057"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 33th FOCS. 620--627","author":"Chvatal V.","unstructured":"V. Chvatal and B. Reed . Mick gets some (the odds are on his side). 1992. Where the really hard problems are . In Proceedings of the 33th FOCS. 620--627 . V. Chvatal and B. Reed. Mick gets some (the odds are on his side). 1992. Where the really hard problems are. In Proceedings of the 33th FOCS. 620--627."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 49th FOCS. 793--802","author":"Coja-Oghlan A.","unstructured":"A. Coja-Oghlan and D. Achlioptas . 2008. Algorithmic barriers from phase transitions . In Proceedings of the 49th FOCS. 793--802 . A. Coja-Oghlan and D. Achlioptas. 2008. Algorithmic barriers from phase transitions. In Proceedings of the 49th FOCS. 793--802."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076516X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(90)90030-E"},{"key":"e_1_2_1_12_1","volume-title":"Low-Density Parity Check Codes","author":"Gallager R. G.","unstructured":"R. G. Gallager . 1963. Low-Density Parity Check Codes . MIT Press . R. G. Gallager. 1963. Low-Density Parity Check Codes. MIT Press."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 43rd ICALP. 65:1--65:12","author":"Hetterich S.","year":"2016","unstructured":"S. Hetterich . 2016 . Analysing survey propagation guided decimation on random formulas . In Proceedings of the 43rd ICALP. 65:1--65:12 . S. Hetterich. 2016. Analysing survey propagation guided decimation on random formulas. In Proceedings of the 43rd ICALP. 65:1--65:12."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20104"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 10th AAAI. 459--465","author":"Levesque H.","unstructured":"H. Levesque , D. Mitchell , and B. Selman . 1992. Hard and easy distribution of SAT problems . In Proceedings of the 10th AAAI. 459--465 . H. Levesque, D. Mitchell, and B. Selman. 1992. Hard and easy distribution of SAT problems. In Proceedings of the 10th AAAI. 459--465."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th SODA. 139--140","author":"Molloy M.","unstructured":"M. Molloy , D. Achlioptas , and P. Beame . 2004. Exponential bounds for DPLL below the satisfiability threshold . In Proceedings of the 15th SODA. 139--140 . M. Molloy, D. Achlioptas, and P. Beame. 2004. Exponential bounds for DPLL below the satisfiability threshold. In Proceedings of the 15th SODA. 139--140."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842867"},{"key":"e_1_2_1_19_1","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","unstructured":"J. Pearl . 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers . J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0703685104"},{"key":"e_1_2_1_21_1","unstructured":"F. Ricci-Tersenghi R. Marino and G. Parisi. 2015. The backtracking survey propagation algorithm for solving random K-SAT problems. arXiv 1508.05117 (2015). F. Ricci-Tersenghi R. Marino and G. Parisi. 2015. The backtracking survey propagation algorithm for solving random K-SAT problems. arXiv 1508.05117 (2015)."},{"key":"e_1_2_1_22_1","volume-title":"Random Graphs","author":"Ruci\u0144ski A.","unstructured":"A. Ruci\u0144ski , S. Janson , and T. \u0141uczak . 2000. Random Graphs . Wiley . A. Ruci\u0144ski, S. Janson, and T. \u0141uczak. 2000. Random Graphs. Wiley."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1074599"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.264.5163.1297"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 24th SAC. 1408--1414","author":"Selman B.","unstructured":"B. Selman , L. Kroc , and A. Sabharwal . 2009. Message-passing and local heuristics as decimation strategies for satisfiability . In Proceedings of the 24th SAC. 1408--1414 . B. Selman, L. Kroc, and A. Sabharwal. 2009. Message-passing and local heuristics as decimation strategies for satisfiability. In Proceedings of the 24th SAC. 1408--1414."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"G. Semerjian and F. Ricci-Tersenghi. 2009. On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms. Journal of Statistical Mechanics (2009) P09001. G. Semerjian and F. Ricci-Tersenghi. 2009. On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms. Journal of Statistical Mechanics (2009) P09001.","DOI":"10.1088\/1742-5468\/2009\/09\/P09001"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 45th Allerton.","author":"Semerjian G.","unstructured":"G. Semerjian , A. Montanari , and F. Ricci-Tersenghi . 2007b. Solving constraint satisfaction problems through belief propagation-guided decimation . In Proceedings of the 45th Allerton. G. Semerjian, A. Montanari, and F. Ricci-Tersenghi. 2007b. Solving constraint satisfaction problems through belief propagation-guided decimation. In Proceedings of the 45th Allerton."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 18th SODA. 1255--1264","author":"Shah D.","unstructured":"D. Shah and A. Montanari . 2007a. Counting good truth assignments of random k-SAT formulae . In Proceedings of the 18th SODA. 1255--1264 . D. Shah and A. Montanari. 2007a. Counting good truth assignments of random k-SAT formulae. In Proceedings of the 18th SODA. 1255--1264."},{"key":"e_1_2_1_29_1","unstructured":"M. Sudan and D. Gamarnik. 2003. The satisfiability threshold of random 3-SAT is at least 3.52. IBM Research Report RC22942 (2003). M. Sudan and D. Gamarnik. 2003. The satisfiability threshold of random 3-SAT is at least 3.52. IBM Research Report RC22942 (2003)."},{"key":"e_1_2_1_30_1","unstructured":"M. Sudan and D. Gamarnik. 2014. Performance of the survey propagation-guided decimation algorithm for the random NAE-K-SAT problem. arXiv 1402.0052 (2014). M. Sudan and D. Gamarnik. 2014. Performance of the survey propagation-guided decimation algorithm for the random NAE-K-SAT problem. arXiv 1402.0052 (2014)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0016"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 47th STOC. 59--68","author":"Sun N.","unstructured":"N. Sun , J. Ding , and A. Sly . 2015. Proof of the satisfiability conjecture for large k . In Proceedings of the 47th STOC. 59--68 . N. Sun, J. Ding, and A. Sly. 2015. Proof of the satisfiability conjecture for large k. In Proceedings of the 47th STOC. 59--68."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IJCAI. 331--337","author":"Taylor W.","unstructured":"W. Taylor , P. Cheeseman , and B. Kanefsky . 1991. Where the really hard problems are . In Proceedings of the IJCAI. 331--337 . W. Taylor, P. Cheeseman, and B. Kanefsky. 1991. Where the really hard problems are. In Proceedings of the IJCAI. 331--337."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/090755862"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 4th SODA. 322--330","author":"Upfal E.","unstructured":"E. Upfal , A. Broder , and A. Frieze . 1993. On the satisfiability and maximum satisfiability of random 3-CNF formulas . In Proceedings of the 4th SODA. 322--330 . E. Upfal, A. Broder, and A. Frieze. 1993. On the satisfiability and maximum satisfiability of random 3-CNF formulas. In Proceedings of the 4th SODA. 322--330."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"R. Urbanke and A. Montanari. 2007c. Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View. R. Urbanke and A. Montanari. 2007c. Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View.","DOI":"10.1016\/S0924-8099(07)80009-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910578"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830900981X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a019"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"M. Wainwright E. Maneva and E. Mossel. 2007. A new look at survey propagation and its generalizations. Journal of the ACM 54 (2007). M. Wainwright E. Maneva and E. Mossel. 2007. A new look at survey propagation and its generalizations. Journal of the ACM 54 (2007).","DOI":"10.1145\/1255443.1255445"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1025"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1073287"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20090"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3005398","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3005398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:50Z","timestamp":1750220630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3005398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,20]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,2,9]]}},"alternative-id":["10.1145\/3005398"],"URL":"https:\/\/doi.org\/10.1145\/3005398","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,20]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}