{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T05:13:47Z","timestamp":1768281227380,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540679967","type":"print"},{"value":"9783540444367","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_12","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T05:33:14Z","timestamp":1182144794000},"page":"108-119","source":"Crossref","is-referenced-by-count":15,"title":["On the Relative Complexity of Approximate Counting Problems"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catherine","family":"Greenhill","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"12_CR1","unstructured":"G.R. Brightwell and P. Winkler, Graph homomorphisms and phase transitions, CDAM Research Report, LSE-CDAM-97-01, Centre for Discrete and Applicable Mathematics, London School of Economics, October 1997."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum, On the Relative Complexity of Approximate Counting Problems, Computer Science Research Report CS-RR-370, University of Warwick, February 2000. http:\/\/www.dcs.warwick.ac.uk\/pub\/index.html","DOI":"10.1007\/3-540-44436-X_12"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"M. Dyer, A. Frieze and M. Jerrum, On counting independent sets in sparse graphs, Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS\u201999), IEEE Computer Society Press, 1999, 210\u2013217.","DOI":"10.1109\/SFFCS.1999.814593"},{"key":"12_CR4","unstructured":"M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms (Extended abstract), Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900), ACM-SIAM 2000, 246\u2013255."},{"key":"12_CR5","unstructured":"R. Fagin, Generalized first-order spectra and polynomial time recognisable sets. In \u201cComplexity of Computation\u201d (R. Karp, ed.), SIAM-AMS Proceedings 7, 1974, 43\u201373."},{"key":"12_CR6","unstructured":"M. Jerrum and A. Sinclair, TheMarkov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.), PWS, 1996, 482\u2013520.reducibility"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"M.R. Jerrum, L.G. Valiant and V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science 43 (1986), 169\u2013188.","journal-title":"Theoretical Computer Science"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R.M. Karp","year":"1989","unstructured":"R.M. Karp, M. Luby and N. Madras, Monte-Carlo approximation algorithms for enumeration problems, Journal of Algorithms 10 (1989), 429\u2013448.","journal-title":"Journal of Algorithms"},{"key":"12_CR9","unstructured":"P.W. Kasteleyn, Graph theory and crystal physics. In Graph Theory and Statistical Physics (F. Harary, ed.), Academic Press, 1967, 43\u2013110."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"J.S. Provan and M.O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected, SIAM Journal on Computing 12 (1983), 777\u20137","journal-title":"SIAM Journal on Computing"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"D. Roth, On the Hardness of approximate reasoning, Artificial Intelligence Journal 82 (1996), 273\u2013302.","journal-title":"Artificial Intelligence Journal"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1006\/jcss.1995.1039","volume":"50","author":"S. Saluja","year":"1995","unstructured":"S. Saluja, K.V. Subrahmanyam and M.N. Thakur, Descriptive complexity of #P functions, Journal of Computer and Systems Sciences 50 (1995), 493\u2013505.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"12_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/3-540-08342-1_37","volume-title":"Proceedings of the 4th International Colloquium on Automata, Languages and Programming (ICALP)","author":"J. Simon","year":"1977","unstructured":"J. Simon, On the difference between one and many (Preliminary version), Proceedings of the 4th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 52, Springer-Verlag, 1977, 480\u2013491."},{"key":"12_CR14","volume-title":"Progress in Theoretical Computer Science","author":"A. Sinclair","year":"1993","unstructured":"A. Sinclair, Algorithms for random generation and counting: a Markov chain approach, Progress in Theoretical Computer Science, Birkh\u00e4user, Boston, 1993."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer, The complexity of approximate counting (preliminary version), Proceedings of the 15th ACM Symposium on Theory of Computing (STOC\u201983), ACM, 1983, 118\u2013126.","DOI":"10.1145\/800061.808740"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing 20 (1991), 865\u2013877.","journal-title":"SIAM Journal on Computing"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant and V.V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science 47 (1986), 85\u201393.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T23:55:16Z","timestamp":1556495716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}