{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:16Z","timestamp":1725600316861},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_48","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T05:20:39Z","timestamp":1313126439000},"page":"567-578","source":"Crossref","is-referenced-by-count":8,"title":["Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Galanis","sequence":"first","affiliation":[]},{"given":"Qi","family":"Ge","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[]},{"given":"Linji","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"48_CR1","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0304-4149(94)90132-5","volume":"49","author":"J. Berg van den","year":"1994","unstructured":"van den Berg, J., Steif, J.E.: Percolation and the hard-core lattice gas model. Stochastic Processes and their Applications\u00a049(2), 179\u2013197 (1994)","journal-title":"Stochastic Processes and their Applications"},{"issue":"5","key":"48_CR2","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1137\/S0097539701383844","volume":"31","author":"M. Dyer","year":"2002","unstructured":"Dyer, M., Frieze, A.M., Jerrum, M.: On counting independent sets in sparse graphs. SIAM J. Comput.\u00a031(5), 1527\u20131541 (2002)","journal-title":"SIAM J. Comput."},{"key":"48_CR3","unstructured":"Galanis, A., Ge, Q., \u0160tefankovi\u010d, D., Vigoda, E., Yang, L.: Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model (2011) Preprint available from the arXiv at, \n                    \n                      http:\/\/arxiv.org\/abs\/1105.5131"},{"issue":"8","key":"48_CR4","doi-asserted-by":"publisher","first-page":"2840","DOI":"10.1063\/1.1697217","volume":"43","author":"D.S. Gaunt","year":"1965","unstructured":"Gaunt, D.S., Fisher, M.E.: Hard-Sphere Lattice Gases. I. Plane-Square Lattice. Journal of Chemical Physics\u00a043(8), 2840\u20132863 (1965)","journal-title":"Journal of Chemical Physics"},{"issue":"1","key":"48_CR5","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/PL00001601","volume":"9","author":"C. Greenhill","year":"2000","unstructured":"Greenhill, C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity\u00a09(1), 52\u201372 (2000)","journal-title":"Computational Complexity"},{"issue":"2-3","key":"48_CR6","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution distribution. Theoretical Computer Science\u00a043(2-3), 169\u2013186 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"48_CR7","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1214\/aoap\/1177005872","volume":"1","author":"F.P. Kelly","year":"1991","unstructured":"Kelly, F.P.: Loss Networks. Annals of Applied Probability\u00a01(3), 319\u2013378 (1991)","journal-title":"Annals of Applied Probability"},{"key":"48_CR8","volume-title":"Markov Chains and Mixing Times","author":"D.A. Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)"},{"issue":"3","key":"48_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#","volume":"10","author":"M. Molloy","year":"1997","unstructured":"Molloy, M., Robalewska, H., Robinson, R.W., Wormald, N.C.: 1-factorizations of random regular graphs. Random Structures and Algorithms\u00a010(3), 305\u2013321 (1997)","journal-title":"Random Structures and Algorithms"},{"issue":"3-4","key":"48_CR10","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(3-4), 401\u2013439 (2009)","journal-title":"Probability Theory and Related Fields"},{"key":"48_CR11","unstructured":"Sly, A.: Computational Transition at the Uniqueness Threshold. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287-296 (2010), Full version available from the arXiv at, \n                    \n                      http:\/\/arxiv.org\/abs\/1005.5584"},{"issue":"3","key":"48_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1516512.1516520","volume":"56","author":"D. \u0160tefankovi\u010d","year":"2009","unstructured":"\u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. Journal of the ACM\u00a056(3), 1\u201336 (2009)","journal-title":"Journal of the ACM"},{"issue":"9","key":"48_CR13","doi-asserted-by":"publisher","first-page":"1021","DOI":"10.1016\/j.jsc.2006.06.004","volume":"41","author":"A.W. Strzebonski","year":"2006","unstructured":"Strzebonski, A.W.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput.\u00a041(9), 1021\u20131038 (2006)","journal-title":"J. Symb. Comput."},{"key":"48_CR14","volume-title":"RAND Corporation, Santa Monica, Calif","author":"A. Tarski","year":"1948","unstructured":"Tarski, A.: RAND Corporation, Santa Monica, Calif. RAND Corporation, Santa Monica (1948)"},{"issue":"3","key":"48_CR15","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The Complexity of Enumeration and Reliability Problems. SIAM J. Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Computing"},{"key":"48_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 (STOC), pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"}],"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-22935-0_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T07:57:37Z","timestamp":1554019057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}