{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:10Z","timestamp":1759638130991},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_44","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"639-654","source":"Crossref","is-referenced-by-count":15,"title":["Improved FPTAS for Multi-spin Systems"],"prefix":"10.1007","author":[{"given":"Pinyan","family":"Lu","sequence":"first","affiliation":[]},{"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"44_CR1","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1002\/rsa.20236","volume":"33","author":"A. Bandyopadhyay","year":"2008","unstructured":"Bandyopadhyay, A., Gamarnik, D.: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Structures & Algorithms\u00a033(4), 452\u2013479 (2008)","journal-title":"Random Structures & Algorithms"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proceedings of STOC, pp. 122\u2013127 (2007)","DOI":"10.1145\/1250790.1250809"},{"key":"44_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Chen, X.: A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. In: Proceedings FOCS, pp. 437\u2013446 (2010)","DOI":"10.1109\/FOCS.2010.49"},{"key":"44_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-642-14165-2_24","volume-title":"Automata, Languages and Programming","author":"J.-Y. Cai","year":"2010","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 275\u2013286. Springer, Heidelberg (2010)"},{"key":"44_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-45726-7_6","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M. Dyer","year":"2002","unstructured":"Dyer, M., Jerrum, M., Vigoda, E.: Rapidly mixing markov chains for dismantleable constraint graphs. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 68\u201377. Springer, Heidelberg (2002)"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Dyer, M.E., Frieze, A.M., Hayes, T.P., Vigoda, E.: Randomly coloring constant degree graphs. In: Proceedings of FOCS, pp. 582\u2013589 (2004)","DOI":"10.1109\/FOCS.2004.57"},{"issue":"1","key":"44_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/jagm.1999.1071","volume":"35","author":"M.E. Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: On markov chains for independent sets. Journal of Algorithms\u00a035(1), 17\u201349 (2000)","journal-title":"Journal of Algorithms"},{"key":"44_CR8","first-page":"1203","volume":"arXiv","author":"A. Galanis","year":"2012","unstructured":"Galanis, A., \u0160tefankovi\u010d, D., Vigoda, E.: Inapproximability of the partition function for the anti-ferromagnetic ising and hard-core models. arXiv preprint arXiv:1203.2226 (2012)","journal-title":"arXiv preprint"},{"key":"44_CR9","first-page":"1305","volume":"arXiv","author":"A. Galanis","year":"2013","unstructured":"Galanis, A., \u0160tefankovi\u010d, D., Vigoda, E.: Inapproximability for anti-ferromagnetic spin systems in the tree non-uniqueness region. arXiv preprint arXiv:1305.2902 (2013)","journal-title":"arXiv preprint"},{"key":"44_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jda.2010.10.002","volume":"12","author":"D. Gamarnik","year":"2012","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting colorings of a graph. Journal of Discrete Algorithms\u00a012, 29\u201347 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"44_CR11","first-page":"1207","volume":"arXiv","author":"D. Gamarnik","year":"2012","unstructured":"Gamarnik, D., Katz, D., Misra, S.: Strong spatial mixing for list coloring of graphs. arXiv preprint arXiv:1207.1223 (2012)","journal-title":"arXiv preprint"},{"issue":"2","key":"44_CR12","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/S0097539704445470","volume":"35","author":"L.A. Goldberg","year":"2005","unstructured":"Goldberg, L.A., Martin, R., Paterson, M.: Strong spatial mixing with fewer colors for lattice graphs. SIAM Journal on Computing\u00a035(2), 486 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-642-22006-7_44","volume-title":"Automata, Languages and Programming","author":"L.A. Goldberg","year":"2011","unstructured":"Goldberg, L.A., Jerrum, M.: A polynomial-time algorithm for estimating the partition function of the ferromagnetic ising model on a regular matroid. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 521\u2013532. Springer, Heidelberg (2011)"},{"issue":"2","key":"44_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1002\/rsa.10090","volume":"23","author":"L.A. Goldberg","year":"2003","unstructured":"Goldberg, L.A., Jerrum, M., Paterson, M.: The computational complexity of two-state spin systems. Random Structures & Algorithms\u00a023(2), 133\u2013154 (2003)","journal-title":"Random Structures & Algorithms"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Hayes, T.P.: Randomly coloring graphs of girth at least five. In: Proceedings of STOC, pp. 269\u2013278 (2003)","DOI":"10.1145\/780542.780584"},{"issue":"2","key":"44_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M. Jerrum","year":"1995","unstructured":"Jerrum, M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms\u00a07(2), 157\u2013166 (1995)","journal-title":"Random Structures & Algorithms"},{"issue":"5","key":"44_CR17","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M. Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the ising model. SIAM Journal on Computing\u00a022(5), 1087\u20131116 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"44_CR18","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M. Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM\u00a051, 671\u2013697 (2004)","journal-title":"Journal of the ACM"},{"key":"44_CR19","first-page":"922","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Liang Li","year":"2012","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: Proceedings of SODA, pp. 922\u2013940 (2012)"},{"key":"44_CR20","first-page":"67","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Liang Li","year":"2013","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: Proceedings of SODA, pp. 67\u201384 (2013)"},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"Luby, M., Vigoda, E.: Approximately counting up to four (extended abstract). In: Proceedings of STOC, pp. 682\u2013687 (1997)","DOI":"10.1145\/258533.258663"},{"key":"44_CR22","doi-asserted-by":"crossref","unstructured":"Restrepo, R., Shin, J., Tetali, P., Vigoda, E., Yang, L.: Improved mixing condition on the grid for counting and sampling independent sets. In: Proceedings of FOCS, pp. 140\u2013149 (2011)","DOI":"10.1109\/FOCS.2011.45"},{"key":"44_CR23","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Srivastava, P., Thurley, M.: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. In: Proceedings of SODA, pp. 941\u2013953 (2012)","DOI":"10.1137\/1.9781611973099.75"},{"issue":"5","key":"44_CR24","doi-asserted-by":"publisher","first-page":"1897","DOI":"10.1214\/07-AAP508","volume":"18","author":"A. Sly","year":"2008","unstructured":"Sly, A.: Uniqueness thresholds on trees versus graphs. The Annals of Applied Probability\u00a018(5), 1897\u20131909 (2008)","journal-title":"The Annals of Applied Probability"},{"key":"44_CR25","doi-asserted-by":"crossref","unstructured":"Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of FOCS, pp. 287\u2013296 (2010)","DOI":"10.1109\/FOCS.2010.34"},{"key":"44_CR26","doi-asserted-by":"crossref","unstructured":"Sly, A., Sun, N.: The computational hardness of counting in two-spin models on d-regular graphs. In: Proceedings of FOCS, pp. 361\u2013369 (2012)","DOI":"10.1109\/FOCS.2012.56"},{"key":"44_CR27","doi-asserted-by":"crossref","unstructured":"Vigoda, E.: Improved bounds for sampling coloring. In: Proceedings of FOCS, pp. 51\u201359 (1999)","DOI":"10.1109\/SFFCS.1999.814577"},{"key":"44_CR28","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of STOC, pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"},{"key":"44_CR29","first-page":"47","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Yitong Yin","year":"2013","unstructured":"Yin, Y., Zhang, C.: Approximate counting via correlation decay on planar graphs. In: Proceedings of SODA, pp. 47\u201366 (2013)"}],"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\/978-3-642-40328-6_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T20:36:28Z","timestamp":1539376588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}