{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:51:55Z","timestamp":1744217515668,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_31","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"380-392","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity"],"prefix":"10.1007","author":[{"given":"Radu","family":"Curticapean","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"31_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/978-3-540-73420-8_69","volume-title":"Automata, Languages and Programming","author":"M Bl\u00e4ser","year":"2007","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the Cover Polynomial. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 801\u2013812. Springer, Heidelberg (2007)"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-540-70575-8_53","volume-title":"Automata, Languages and Programming","author":"AA Bulatov","year":"2008","unstructured":"Bulatov, A.A.: The Complexity of the Counting Constraint Satisfaction Problem. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 646\u2013661. Springer, Heidelberg (2008)"},{"key":"31_CR3","first-page":"909","volume":"2012","author":"J-Y Cai","year":"2012","unstructured":"Cai, J.-Y., Chen, X.: Complexity of counting CSP with complex weights. STOC 2012, 909\u2013920 (2012)","journal-title":"STOC"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-642-02017-9_17","volume-title":"Theory and Applications of Models of Computation","author":"J-Y Cai","year":"2009","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: A Computational Proof of Complexity of Some Restricted Counting Problems. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol. 5532, pp. 138\u2013149. Springer, Heidelberg (2009)"},{"key":"31_CR5","first-page":"1714","volume":"2011","author":"J Cai","year":"2011","unstructured":"Cai, J., Pinyan, L., Xia, M.: Dichotomy for Holant* problems of boolean domain. SODA 2011, 1714\u20131728 (2011)","journal-title":"SODA"},{"issue":"2","key":"31_CR6","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(92)90234-7","volume":"102","author":"P Dagum","year":"1992","unstructured":"Dagum, P., Luby, M.: Approximating the permanent of graphs with large factors. Theor. Comput. Sci. 102(2), 283\u2013305 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"31_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahlen, M.: Exponential time complexity of the permanent and the tutte polynomial. ACM Transactions on Algorithms 10(4), 21 (2014)","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"31_CR8","doi-asserted-by":"publisher","first-page":"1921","DOI":"10.1137\/12088330X","volume":"43","author":"Leslie Ann Goldberg and Mark Jerrum","year":"2014","unstructured":"Leslie Ann Goldberg and Mark Jerrum: The complexity of computing the sign of the tutte polynomial. SIAM J. Comput. 43(6), 1921\u20131952 (2014)","journal-title":"SIAM J. Comput."},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-17493-3_18","volume-title":"Parameterized and Exact Computation","author":"C Hoffmann","year":"2010","unstructured":"Hoffmann, C.: Exponential Time Complexity of Weighted Counting of Independent Sets. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 180\u2013191. Springer, Heidelberg (2010)"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-17493-3_19","volume-title":"Parameterized and Exact Computation","author":"T Husfeldt","year":"2010","unstructured":"Husfeldt, T., Taslaman, N.: The Exponential Time Complexity of Computing the Probability That a Graph Is Connected. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 192\u2013203. Springer, Heidelberg (2010)"},{"issue":"4","key":"31_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Computer and Sys. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Computer and Sys. Sci."},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D J.A.: On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society 108(1), 35\u201353 (1990)","DOI":"10.1017\/S0305004100068936"},{"issue":"4","key":"31_CR13","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. J. ACM 51(4), 671\u2013697 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"31_CR14","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"N Linial","year":"1986","unstructured":"Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM Journal on Algebraic and Discrete Methods 7(2), 331\u2013335 (1986)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"31_CR15","first-page":"173","volume":"327","author":"AD Sokal","year":"2005","unstructured":"Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. Surveys in Combinatorics 327, 173\u2013226 (2005)","journal-title":"Surveys in Combinatorics"},{"issue":"2","key":"31_CR16","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"31_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science 8(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:24:30Z","timestamp":1674228270000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}