{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:36Z","timestamp":1725490236884},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642317699"},{"type":"electronic","value":"9783642317705"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31770-5_30","type":"book-chapter","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T05:03:12Z","timestamp":1343278992000},"page":"336-347","source":"Crossref","is-referenced-by-count":1,"title":["Inapproximability after Uniqueness Phase Transition in Two-Spin Systems"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Heng","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Pinyan","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02280291","volume":"18","author":"L. Lov\u00e1sz","year":"1967","unstructured":"Lov\u00e1sz, L.: Operations with structures. Acta Mathematica Hungarica\u00a018, 321\u2013328 (1967)","journal-title":"Acta Mathematica Hungarica"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Dyer, M., Greenhill, C.: The complexity of counting graph homomorphisms. In: Proceedings of the 9th International Conference on Random Structures and Algorithms, pp. 260\u2013289 (2000)","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.3.CO;2-N"},{"issue":"2-3","key":"30_CR4","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2005.09.011","volume":"348","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Grohe, M.: The complexity of partition functions. Theoretical Computer Science\u00a0348(2-3), 148\u2013186 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"30_CR5","doi-asserted-by":"publisher","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"L. Goldberg","year":"2010","unstructured":"Goldberg, L., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing\u00a039(7), 3336\u20133402 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. In: Proceedings of the 37th Colloquium on Automata, Languages and Programming (2010); To appear in SIAM Journal on Computing","DOI":"10.1007\/978-3-642-14165-2_24"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"Dyer, M., Goldberg, L., Paterson, M.: On counting homomorphisms to directed acyclic graphs. Journal of the ACM\u00a054(6) (2007)","DOI":"10.1145\/1314690.1314691"},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Chen, X.: A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 437\u2013446 (2010)","DOI":"10.1109\/FOCS.2010.49"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: The complexity of the counting constraint satisfaction problem. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 646\u2013661 (2008)","DOI":"10.1007\/978-3-540-70575-8_53"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Dyer, M., Richerby, D.: On the complexity of #CSP. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 725\u2013734 (2010)","DOI":"10.1145\/1806689.1806789"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Chen, X., Lu, P.: Non-negatively weighted #CSP: An effective complexity dichotomy. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, pp. 45\u201354 (2011)","DOI":"10.1109\/CCC.2011.32"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Chen, X.: Complexity of counting CSP with complex weights. In: Proceedings of the 44th ACM Symposium on Theory of Computing (2012)","DOI":"10.1145\/2213977.2214059"},{"issue":"5","key":"30_CR13","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"},{"issue":"2","key":"30_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1002\/rsa.10090","volume":"23","author":"L. Goldberg","year":"2003","unstructured":"Goldberg, L., Jerrum, M., Paterson, M.: The computational complexity of two-state spin systems. Random Structures and Algorithms\u00a023(2), 133\u2013154 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1137\/S0097539701383844","volume":"31","author":"M. Dyer","year":"2002","unstructured":"Dyer, M., Frieze, A., Jerrum, M.: On counting independent sets in sparse graphs. SIAM Journal on Computing\u00a031, 1527\u20131541 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"},{"key":"30_CR17","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 the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012)","DOI":"10.1137\/1.9781611973099.75"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012)","DOI":"10.1137\/1.9781611973099.74"},{"key":"30_CR19","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. arXiv:1111.7064 (2011)"},{"key":"30_CR20","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 and Algorithms\u00a033, 452\u2013479 (2008)","journal-title":"Random Structures and Algorithms"},{"key":"30_CR21","doi-asserted-by":"crossref","unstructured":"Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science (2010)","DOI":"10.1109\/FOCS.2010.34"},{"key":"30_CR22","doi-asserted-by":"crossref","unstructured":"Galanis, A., Ge, Q., \u0160tefankovi\u010d, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. In: Proceedings of the 15th International Workshop on Randomization and Computation, pp. 567\u2013578 (2011)","DOI":"10.1007\/978-3-642-22935-0_48"},{"key":"30_CR23","unstructured":"Cai, J.Y., Chen, X., Guo, H., Lu, P.: Inapproximability after uniqueness phase transition in two-spin systems. University of Wisconsin, Madison CS Technical Report (2011), \n                  \n                    http:\/\/digital.library.wisc.edu\/1793\/61488"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00440-007-0131-9","volume":"143","author":"E. Mossel","year":"2009","unstructured":"Mossel, E., Weitz, D., Wormald, N.: On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields\u00a0143, 401\u2013439 (2009)","journal-title":"Probability Theory and Related Fields"},{"key":"30_CR25","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. Journal of the ACM\u00a048, 798\u2013859 (2001)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31770-5_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:47:49Z","timestamp":1620128869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31770-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642317699","9783642317705"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31770-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}