{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:10:07Z","timestamp":1736525407299,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540380443"},{"type":"electronic","value":"9783540380450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_32","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"339-350","source":"Crossref","is-referenced-by-count":14,"title":["Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Ben-Sasson, E.: Linear upper bounds for random walk on small density random 3-cnf. In: Proc. 44th IEEE Symp. on Found. of Comp. Science, pp. 352\u2013361 (2003)","DOI":"10.1109\/SFCS.2003.1238209"},{"issue":"6","key":"32_CR2","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM J. on Comput.\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM J. on Comput."},{"key":"32_CR3","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":"32_CR4","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-cnf formulas. In: Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 322\u2013330 (1993)"},{"key":"32_CR5","unstructured":"Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-sat formulae and the satisfiability threshold. In: Proc. 11th ACM-SIAM Symp. on Discrete Algorithms, pp. 126\u2013127 (2000)"},{"issue":"2","key":"32_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A","volume":"16","author":"U. Feige","year":"2000","unstructured":"Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. Random Structures and Algorithms\u00a016(2), 195\u2013208 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"32_CR7","unstructured":"Feige, U., Vilenchik, D.: A local search algorithm for 3SAT. Technical report, The Weizmann Institute of Science (2004)"},{"key":"32_CR8","unstructured":"Flaxman, A.: A spectral technique for random satisfiable 3CNF formulas. In: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms, pp. 357\u2013363 (2003)"},{"issue":"4","key":"32_CR9","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E.: Sharp thresholds of graph properties, and the k-sat problem. J. Amer. Math. Soc.\u00a012(4), 1017\u20131054 (1999)","journal-title":"J. Amer. Math. Soc."},{"issue":"1-2","key":"32_CR10","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A.M. Frieze","year":"1997","unstructured":"Frieze, A.M., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms\u00a010(1-2), 5\u201342 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","volume":"IT-8","author":"T.G. Gallager","year":"1962","unstructured":"Gallager, T.G.: Low-density parity-check codes. IRE. Trans. Info. Theory\u00a0IT-8, 21\u201328 (1962)","journal-title":"IRE. Trans. Info. Theory"},{"issue":"4","key":"32_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Hui, C., Frieze, A.M.: Coloring bipartite hypergraphs. In: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, pp. 345\u2013358 (1996)","DOI":"10.1007\/3-540-61310-2_26"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/3-540-45749-6_51","volume-title":"Algorithms - ESA 2002","author":"A.C. Kaporis","year":"2002","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 574\u2013585. Springer, Heidelberg (2002)"},{"issue":"1","key":"32_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(92)90029-U","volume":"43","author":"E. Koutsoupias","year":"1992","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the greedy algorithm for satisfiability. Info. Process. Letters\u00a043(1), 53\u201355 (1992)","journal-title":"Info. Process. Letters"},{"issue":"2","key":"32_CR16","doi-asserted-by":"publisher","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), 498\u2013519 (2001)","journal-title":"IEEE Transactions on Information Theory"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.: Analysis of low density parity check codes and improved designs using irregular graphs. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 249\u2013258 (1998)","DOI":"10.1145\/276698.276756"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1109\/18.910575","volume":"47","author":"M. Luby","year":"2001","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.: Efficient erasure correcting codes. IEEE Trans. Info. Theory\u00a047, 569\u2013584 (2001)","journal-title":"IEEE Trans. Info. Theory"},{"key":"32_CR19","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers Inc., San Francisco (1988)"},{"key":"32_CR20","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1109\/18.910578","volume":"47","author":"T. Richardson","year":"2001","unstructured":"Richardson, T., Shokrollahi, A., Urbanke, R.: Design of capacity-approaching irregular low-density parity check codes. IEEE Trans. Info. Theory\u00a047, 619\u2013637 (2001)","journal-title":"IEEE Trans. Info. Theory"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T15:29:19Z","timestamp":1736522959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11830924_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}