{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T19:29:31Z","timestamp":1648582171499},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,1,27]],"date-time":"2009-01-27T00:00:00Z","timestamp":1233014400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00224-009-9179-5","type":"journal-article","created":{"date-parts":[[2009,1,26]],"date-time":"2009-01-26T16:42:14Z","timestamp":1232988134000},"page":"926-942","source":"Crossref","is-referenced-by-count":0,"title":["Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions"],"prefix":"10.1007","volume":"45","author":[{"given":"Mikael","family":"Onsj\u00f6","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,27]]},"reference":[{"key":"9179_CR1","doi-asserted-by":"crossref","unstructured":"Boppana, R.B.: Eigenvalues and graph bisection: an average-case analysis. In: Proc. Symposium on Foundations of Computer Science, pp. 280\u2013285 (1987)","DOI":"10.1109\/SFCS.1987.22"},{"issue":"3","key":"9179_CR2","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 spectral heuristic for bisecting random graphs. Random Struct. Algorithms 29(3), 351\u2013398 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"9179_CR3","doi-asserted-by":"crossref","unstructured":"Dubhashi, D., Laura, L., Panconesi, A.: Analysis and experimental evaluation of a simple algorithm for collaborative filtering in planted partition models. In: Proc. FST TCS 2003, pp. 168\u2013182 (2003)","DOI":"10.1007\/978-3-540-24597-1_15"},{"issue":"21","key":"9179_CR4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","volume":"IT-8","author":"R.G. Gallager","year":"1962","unstructured":"Gallager, R.G.: Low density parity check codes. IRE Trans. Inf. Theory IT-8(21), 21\u201328 (1962)","journal-title":"IRE Trans. Inf. Theory"},{"key":"9179_CR5","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Bell Telephone Laboratories, Incorporated (1979)"},{"issue":"1\u20133","key":"9179_CR6","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M. Jerrum","year":"1998","unstructured":"Jerrum, M., Sorkin, G.: The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82(1\u20133), 155\u2013175 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9179_CR7","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/18.910576","volume":"47","author":"M. Luby","year":"2001","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, M., Spielman, D.: Improved low-density parity-check codes using irregular graphs. IEEE Trans. Inf. Theory 47(2), 585\u2013598 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"9179_CR8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1109\/18.748992","volume":"IT-45","author":"D. MacKay","year":"1999","unstructured":"MacKay, D.: Good error-correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory IT-45(2), 399\u2013431 (1999)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9179_CR9","doi-asserted-by":"crossref","unstructured":"McEliece, R., MacKay, D., Cheng, J.: Turbo decoding as an instance of Pearl\u2019s \u201cBelief Propagation\u201d algorithm. IEEE J. Sel. Areas Comm. 16(2) 1998","DOI":"10.1109\/49.661103"},{"key":"9179_CR10","unstructured":"McSherry, F.: Spectral partition of random graphs. In: Proc. 40th IEEE Sympos. on Foundations of Computer Science (FOCS\u201999). IEEE (1999)"},{"key":"9179_CR11","unstructured":"Onsj\u00f6, M., Watanabe, O.: Simple algorithms for graph partition problems. Research Report C-212. Dept. of Math. and Comput. Sci., Tokyo Inst. of Tech. (2005)"},{"key":"9179_CR12","series-title":"LNCS","first-page":"507","volume-title":"Proc. 17th Int\u2019l Sympos. on Algorithms and Computation (ISAAC\u201906)","author":"M. Onsj\u00f6","year":"2006","unstructured":"Onsj\u00f6, M., Watanabe, O.: A simple message passing algorithm for graph partition problem. In: Proc. 17th Int\u2019l Sympos. on Algorithms and Computation (ISAAC\u201906). LNCS, vol. 4288, pp. 507\u2013516. Springer, Berlin (2006)"},{"key":"9179_CR13","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":"9179_CR14","series-title":"LNCS","first-page":"277","volume-title":"Proc. 9th Int\u2019l Conference on Theory and Application of Satisfiability Testing (SAT\u201906)","author":"O. Watanabe","year":"2006","unstructured":"Watanabe, O., Yamamoto, M.: Average-case analysis for the MAX-2SAT problem. In: Proc. 9th Int\u2019l Conference on Theory and Application of Satisfiability Testing (SAT\u201906). LNCS, vol. 4142, pp. 277\u2013282. Springer, Berlin (2006)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9179-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9179-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9179-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:37Z","timestamp":1558698697000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9179-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,27]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9179"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9179-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,27]]}}}