{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:14:56Z","timestamp":1781014496309,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540372066","type":"print"},{"value":"9783540372073","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11814948_31","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T10:12:38Z","timestamp":1153217558000},"page":"325-338","source":"Crossref","is-referenced-by-count":7,"title":["Characterizing Propagation Methods for Boolean Satisfiability"],"prefix":"10.1007","author":[{"given":"Eric I.","family":"Hsu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheila A.","family":"McIlraith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A. Braunstein","year":"2005","unstructured":"Braunstein, A., Mezard, M., Zecchina, R.: Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms\u00a027, 201\u2013226 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"K. Kask","year":"2004","unstructured":"Kask, K., Dechter, R., Gogate, V.: Counting-based look-ahead schemes for constraint satisfaction. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, Springer, Heidelberg (2004)"},{"key":"31_CR3","unstructured":"Wang, Y., Zhang, J., Fossorier, M., Yedidia, J.: Reduced latency iterative decoding of LDPC codes. In: IEEE Conference on Global Telecommunications (GLOBECOM) (2005)"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Braunstein, A., Zecchina, R.: Learning by message passing in networks of discrete synapses. Physics Review Letters\u00a096(5) (2006)","DOI":"10.1103\/PhysRevLett.96.030201"},{"key":"31_CR5","volume-title":"Probabilistic Reasoning in Intelligent Systems","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo (1988)"},{"issue":"2","key":"31_CR6","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"F.R. Kschischang","year":"2001","unstructured":"Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory\u00a047(2) (2001)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Braunstein, A., Zecchina, R.: Survey propagation as local equilibrium equations. Journal of Statistical Mechanics: Theory and Experiments\u00a0PO6007 (2004)","DOI":"10.1088\/1742-5468\/2004\/06\/P06007"},{"key":"31_CR8","first-page":"239","volume-title":"Exploring Artificial Intelligence in the New Millennium","author":"J. Yedidia","year":"2003","unstructured":"Yedidia, J., Freeman, W., Weiss, Y.: Understanding belief propagation and its generalizations. In: Nebel, B., Lakemeyer, G. (eds.) Exploring Artificial Intelligence in the New Millennium, pp. 239\u2013256. Morgan Kaufmann, San Francisco (2003)"},{"key":"31_CR9","unstructured":"Dechter, R., Mateescu, R.: A simple insight into properties of iterative belief propagation. In: Proc. of 19th International Conference on Uncertainty in Artificial Intelligence (UAI 2003), Acapulco, Mexico (2003)"},{"key":"31_CR10","unstructured":"Lardeux, F., Saubion, F., Hao, J.K.: Three Truth Values for the SAT and MAX-SAT Problems. In: Proc. of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005), Edinburgh, Scotland (2005)"},{"issue":"7","key":"31_CR11","doi-asserted-by":"publisher","first-page":"2282","DOI":"10.1109\/TIT.2005.850085","volume":"51","author":"J. Yedidia","year":"2005","unstructured":"Yedidia, J., Freeman, W., Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory\u00a051(7), 2282\u20132312 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"31_CR12","unstructured":"Dechter, R., Kask, K., Mateescu, R.: Iterative join-graph propagation. In: Proc. of 18th International Conference on Uncertainty in Artificial Intelligence (UAI 2002), Edmonton, Canada, pp. 128\u2013136 (2002)"},{"issue":"1-2","key":"31_CR13","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.artint.2005.04.004","volume":"166","author":"Kalev Kask","year":"2005","unstructured":"Kask, K., Dechter, R., Larrosa, J., Pfeffer, A.: Cluster-tree decompostitions for reasoning in graphical models. Artificial Intelligence\u00a0166(1-2) (2005)","journal-title":"Artificial Intelligence"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H., Cohen, B.: Local search strategies for satisfiability testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science\u00a026 (1996)","DOI":"10.1090\/dimacs\/026\/25"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M. Goemans","year":"1994","unstructured":"Goemans, M., Williamson, D.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics\u00a07, 656\u2013666 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a0(42), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"31_CR17","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Proc. of 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico (2003)"},{"issue":"1-2","key":"31_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1023\/A:1006314320276","volume":"24","author":"C. Gomes","year":"2000","unstructured":"Gomes, C., Selman, B., Crato, N., Kautz, H.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning\u00a024(1-2), 67\u2013100 (2000)","journal-title":"Journal of Automated Reasoning"},{"issue":"1","key":"31_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"A. Dempster","year":"1977","unstructured":"Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society\u00a039(1), 1\u201339 (1977)","journal-title":"Journal of the Royal Statistical Society"},{"issue":"1","key":"31_CR20","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1023\/A:1008287028851","volume":"12","author":"Y. Shang","year":"1998","unstructured":"Shang, Y., Wah, B.: A discrete Lagrangian-based global-search method for solving satisfiability problems. Journal of Global Optimization\u00a012(1), 61\u201399 (1998)","journal-title":"Journal of Global Optimization"},{"key":"31_CR21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/978-94-011-5014-9_12","volume-title":"Learning in Graphical Models","author":"R. Neal","year":"1998","unstructured":"Neal, R., Hinton, G.: A view of the EM algorithm that justifies incremental, sparse, and other variants. In: Jordan, M. (ed.) Learning in Graphical Models, pp. 355\u2013368. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"31_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-011-5014-9","volume-title":"Learning in Graphical Models","author":"M. Jordan","year":"1998","unstructured":"Jordan, M., Ghahramani, Z., Jaakkola, T., Saul, L.: An introduction to variational methods for graphical models. In: Jordan, M. (ed.) Learning in Graphical Models, MIT Press, Cambridge (1998)"},{"key":"31_CR23","unstructured":"Braunstein, A., Leone, M., Mezard, M., Weigt, M., Zecchina, R.: Sp-1.3 survey propagatrion implementation, http:\/\/www.ictp.trieste.it\/~zecchina\/SP\/"},{"key":"31_CR24","unstructured":"Hsu, E., McIlraith, S.: Characterizing loopy belief propagation as expectation maximization (2006), Manuscript in preparation"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814948_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T23:23:25Z","timestamp":1736465005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814948_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540372066","9783540372073"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11814948_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}