{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T20:55:48Z","timestamp":1649019348819},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T00:00:00Z","timestamp":1362441600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s00453-013-9762-7","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T00:52:14Z","timestamp":1362444734000},"page":"848-868","source":"Crossref","is-referenced-by-count":4,"title":["Message Passing Algorithms for MLS-3LIN Problem"],"prefix":"10.1007","volume":"66","author":[{"given":"Osamu","family":"Watanabe","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,5]]},"reference":[{"issue":"6","key":"9762_CR1","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A\u00a0spectral technique for coloring random 3-colorable graphs. SIAM J. Comput. 26(6), 1733\u20131748 (1997)","journal-title":"SIAM J. Comput."},{"key":"9762_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-642-04944-6_10","volume-title":"Proceedings of the 5th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA\u201909)","author":"R. Berke","year":"2009","unstructured":"Berke, R., Onsj\u00f6, M.: Propagation connectivity of random hypergraphs. In: Proceedings of the 5th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA\u201909). Lecture Notes in Computer Science, vol. 5792, pp. 117\u2013126 (2009)"},{"issue":"3","key":"9762_CR3","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1002\/rsa.20116","volume":"29","author":"A. Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A.: A\u00a0spectral heuristic for bisecting random graphs. Random Struct. Algorithms 29(3), 351\u2013398 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"1\u20133","key":"9762_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2004.07.017","volume":"329","author":"A. Coja-Oghlan","year":"2004","unstructured":"Coja-Oghlan, A., Goerdt, A., Lanka, A., Sch\u00e4dlich, F.: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theor. Comput. Sci. 329(1\u20133), 1\u201345 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9762_CR5","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1017\/S096354830900981X","volume":"18","author":"A. Coja-Oghlan","year":"2009","unstructured":"Coja-Oghlan, A., Mossel, E., Vilenchnik, D.: A\u00a0spectral approach to analyzing belief propagation for 3-coloring. Comb. Probab. Comput. 18(6), 881\u2013912 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"9762_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/978-3-642-15369-3_37","volume-title":"Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM\u201910)","author":"A. Coja-Oghlan","year":"2010","unstructured":"Coja-Oghlan, A., Onjs\u00f6, M., Watanabe, O.: Propagation connectivity of random hypergraphs. In: Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM\u201910). Lecture Notes in Computer Science, vol. 6302, pp. 490\u2013503 (2010). The final version appears in Electron. J. Comb. 19(P17), 1\u201325 (2012)"},{"issue":"2","key":"9762_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U. Feige","year":"2005","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2), 251\u2013275 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"9762_CR8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/SFCS.2005.74","volume-title":"Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS\u201905)","author":"S.A. Khot","year":"2005","unstructured":"Khot, S.A., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1. In: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 53\u201362. IEEE Press, New York (2005)"},{"key":"9762_CR9","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, San Mateo (1988)"},{"key":"9762_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/11940128_51","volume-title":"Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC\u201906)","author":"M. Onsj\u00f6","year":"2006","unstructured":"Onsj\u00f6, M., Watanabe, O.: A\u00a0simple message passing algorithm for graph partition problem. In: Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC\u201906). Lecture Notes in Computer Science, vol. 4288, pp. 507\u2013516 (2006)"},{"key":"9762_CR11","unstructured":"Watanabe, O., Yamamoto, M.: Belief propagation and spectral methods. Research Report of Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, C-248 (2007)"},{"issue":"16\u201318","key":"9762_CR12","doi-asserted-by":"crossref","first-page":"1685","DOI":"10.1016\/j.tcs.2009.12.020","volume":"411","author":"O. Watanabe","year":"2010","unstructured":"Watanabe, O., Yamamoto, M.: Average-case analysis for the MAX-2SAT problem. Theor. Comput. Sci. 411(16\u201318), 1685\u20131697 (2010)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9762-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9762-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9762-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:11Z","timestamp":1559137511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9762-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,5]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9762"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9762-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,5]]}}}